[BOJ, 백준] 1916 최소비용 구하기 python

 

 

 

 

Well-known인 다익스트라 알고리즘. ...

 

처음에 실수로 가중치가 왕복으로 주어지는줄 알았는데, 그게 아니라 편도였던 것....

 

수정하니 바로 맞는 결과가 나왔다.

import sys
import heapq
input = sys.stdin.readline
N = int(input())
M = int(input())
gp = [[] for _ in range (0,N+1)]
for _ in range (0,M):
    a,b,cost = map(int,input().split())
    gp[a].append((b,cost))
start, end = map(int,input().split())
INF = int(1e9)
dist = [INF for _ in range (0,N+1)]
q = []
dist[start] = 0
heapq.heappush(q, (dist[start], start))
while q:
    distance, node = heapq.heappop(q)
    if dist[node] < distance:
        continue
    for next, next_dist in gp[node]:
        d = distance + next_dist
        if d < dist[next]:
            dist[next] = d
            heapq.heappush(q, (dist[next], next))
print(dist[end])