우주의 IT 소행성

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

import sys
import heapq
input = sys.stdin.readline
v, e = map(int, input().split())
start = int(input())

graph = [[] for _ in range(v + 1)]
for _ in range(e):
    x, y, z = map(int, input().split())
    graph[x].append((z, y))

cost = [float('inf')] * (v + 1)
cost[start] = 0
queue = []
heapq.heappush(queue, (0, start))

while queue:
    weight, node = heapq.heappop(queue)

    if cost[node] < weight:
        continue
    for w, n in graph[node]:
        if weight + w < cost[n]:
            cost[n] = weight + w
            heapq.heappush(queue, (cost[n], n))

for i in cost[1:]:
    print(i if i != float('inf') else "INF")

dijkstra 기본 문제인 최단 경로 문제이다.

heapq를 이용해 우선순위 큐처럼 사용했는데 한가지 간과한 점은

우선순위를 node 정보가 아닌 cost정보가 먼저 오도록 해야 한다는 것이다.

node 정보를 우선순위로 한다면 시간초과가 나니 주의!