[백준] 1916

최소비용 구하기 (1916번)

• 사이트/난이도: 백준 / 골드5
• 코드

# 골드5 최소비용 구하기
import sys
import heapq
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

start, end = map(int, input().split())

INF = int(1e9)
distance = [INF] * (n+1)

def dijkstra():
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = i[1] + dist
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra()
print(distance[end])

• 느낀점
  • 기본적인 다익스트라 문제
  • n과 m의 크기가 1000, 100000 이므로 시간복잡도가 O(nlogm)인 다익스트라를 이용한다.
  • 그리고 출발점과 도착점이 정해지기 때문에 출발점에서 모든 거리를 구할수 있는 다익스트라를 이용했다.
  • 이 때, heapq 우선순위 큐를 써서 현재 처리하는 도시에서 가장 거리가 짧은 도시를 처리할수 있도록 하였다.