핵심 아이디어

<aside> 💡 다익스트라 알고리즘을 이용해 graph에 정점과 간선을 저장하고,

시작 노드부터 연결된 노드들과의 거리를 비교해서 최솟값으로 업데이트해주는 과정 반복

우선순위 큐 : 가장 작은 값이 먼저 나오도록 함. 최단 거리가 업데이트 되면 이와 연관된 노드들의 거리를 다시 탐색하기 위해 큐에 넣어 줌.

</aside>

코드

import sys
import heapq

def dijkstra(start) :
    q= []
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q :
        d, now = heapq.heappop(q)

        if dist[now] < d :
            continue

        for i in graph[now] :
            cost = d + i[1]
            if cost < dist[i[0]] :
                dist[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

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

graph = [[] for i in range(V+1)]
dist = [INF] * (V+1) 

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append((v, w))

dijkstra(s)

for i in range(1, V+1) :
    if dist[i] == INF :
        print("INF")
    else :
        print(dist[i])