[다익스트라 알고리즘] 최소비용 구하기

기출 : 백준 #1916

 

일반적인 다익스트라 문제이다

from heapq import heappush, heappop
INF = int(1e9)

n = int(input())
m = int(input())


distance = [INF for _ in range(n+1)]
graph = [[] for _ in range(n+1)]

for _ in range(m):
    x, y, w = map(int,input().split())
    graph[x].append([w,y])


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


def djikstra(start):
    queue = list()
    distance[start] = 0
    heappush(queue, (0,start))
    while queue:
        curVal, cur = heappop(queue)
        if distance[cur] < curVal:
            continue
        for nextVal, next in graph[cur]:
            if distance[next] > curVal + nextVal:
                distance[next] = curVal + nextVal
                heappush(queue, (curVal + nextVal, next))

djikstra(start)
print(distance[end])