Heat Wave[백준 5996]

https://www.acmicpc.net/problem/5996

 

전형적인 최단경로 찾기 문제입니다. 

import heapq 
t,c,ts,te =map(int,input().split())
gra =[[] for _ in range(t+1)]
inf = 1e9 
def dijk(start,end):
    dp=[inf]*(t+1)
    dp[start] = 0 
    heap=[]
    heapq.heappush(heap,(0,start))
    while heap:
        wei,now =heapq.heappop(heap)
        if wei > dp[now] :continue 
        for nextnode,cost in gra[now]:
            if dp[nextnode] > wei+cost :
                dp[nextnode] = wei+cost 
                heapq.heappush(heap, (wei+cost, nextnode))
                
    return dp[end] 


for _ in range(c):
    a,b,c=map(int, input().split())
    gra[a].append((b,c)) 
    gra[b].append((a,c))
print(dijk(ts,te))