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

어떤노드에 처음으로 방문한 순간이 최단거리임이 보장된다(bfs와 비슷).

따라서 주어진 끝노드에 도달하면 해당 비용을 출력한 후 종료한다.

import heapq

N=int(input())
M=int(input())
graph={}
for i in range(N):
    graph[i+1]=[]
for i in range(M):
    a,b,c=map(int,input().split())
    graph[a].append([b,c])
start,end=map(int,input().split())

maxNum=9876543210
nodeDist=[maxNum for i in range(N+1)]
dij=[[0,start]]
heapq.heapify(dij)
while(dij):

    temp=heapq.heappop(dij)
    nowCost=temp[0]
    nowNode=temp[1]

    if nowNode==end:
        print(nowCost)
        break

    if nodeDist[nowNode]<nowCost:
        continue
    for toNode,toCost in graph[nowNode]:
        w=nowCost+toCost
        if nodeDist[toNode]>w:
            nodeDist[toNode]=w
            heapq.heappush(dij,[w,toNode])