알고리즘 1753 최단경로

과정

• 다익스트라
• 한 점에서 다른 곳으로 가는 최단 거리를 구하기

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())

INF = 1e9
graph = [[] for _ in range(V)] # 노드 연결 정보 저장
distance = [INF] * V # 각 노드까지의 최소 거리를 저장
start = int(input())-1

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u-1].append((v-1, w)) # (노드, 거리) 순으로 저장

def dijkstra(start):
    # 초기화
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q: # q 의 값을 하나씩 빼면서 볼 것임
        dist, now = heapq.heappop(q)
        if distance[now] < dist: # 이미 처리한 경우 ( distance보다 크다는 말은 이전에 heapq로 작은 값을 처리했다는 뜻)
            continue
        for i in graph[now]: # now와 연결된 모든 노드에 대해서
            cost = dist + i[1]

            if distance[i[0]] > cost: # 최단 거리를 업데이트 해야하면
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)
for i in distance:
    if i != INF:
        print(i)
    else:
        print("INF")