最短パス

白駿1753

優先キューを使用したマルチアウトプットアルゴリズム

import sys
import heapq


V, E = map(int, sys.stdin.readline().split())
s = int(sys.stdin.readline())

graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    #첫번째 원소를 기준으로 우선순위를 설정하므로 w가 우선순위 값이 되도록 w먼저
    graph[u].append((w,v))

inf = sys.maxsize
dp = [inf]*(V+1)

heap = []
def dk(s):
    #시작노드로 가기 위한 최단경로는 0으로 설정하여 큐에 삽입
    dp[s] = 0
    heapq.heappush(heap,(0, s))

    while heap:
        nw, nn = heapq.heappop(heap)
        #현재 dp와 비교하여 가중치가 더 큰 튜플이면 무시
        #이미 now_node에 now_w보다 더 짧은 길이로 방문한 적이 있다면
        if dp[nn] < nw:
            continue
        #현재 노드와 연결된 다른 인접노드 확인
        for ad_w, ad_n in graph[nn]:
            #현재 정점까지의 가중치+현재에서 다음 정점까지의 가중치
            if nw+ad_w < dp[ad_n]: #현재 노드를 거치는게 더 짧은 경우
                dp[ad_n] = nw+ad_w
                heapq.heappush(heap, (nw+ad_w, ad_n))

dk(s)
for ele in dp[1:]:
    if ele==inf:
        print("INF")
    else:
        print(ele)