[snippet] dijkstra.py

백준 1753번. 최단경로에 대한 풀이를 Dijkstra's Algorithm의 스니펫 느낌으로 작성.

• 한 정점에서 다른 모든 정점까지의 Shortest Path(최단 경로) 를 구할 때 사용.
  (단, 가중치는 모두 양수여야 함.)

import sys
import heapq
input = lambda: sys.stdin.readline().rstrip()
INF = int(1e9)

V, E = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, weight = map(int, input().split())
    graph[u].append((v, weight))

#########################

def dijkstra(start):
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        w, now = heapq.heappop(q)
        if dist[now] < w: # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            continue
        for next_, next_w in graph[now]:
            cost = w + next_w
            if cost < dist[next_]:
                dist[next_] = cost
                heapq.heappush(q, (cost, next_))

dist = [INF] * (V+1) # 1-indexed
dijkstra(start)

#########################

for d in dist[1:]:
    print(d if d != INF else 'INF')