BOJ 1753 최단경로

https://www.acmicpc.net/problem/1753
시간 1초, 메모리 256MB
input :

• V E (1<= V <= 20,000)(1 <= E <= 300,000)
• 시작 정점 K
• 각 간선을 나타내는 3개의 정수 (u, v, w) u에서 v로 가는 비용 w인 간선이 존재.
  (u != v, 1 <= w <= 10)

output :

• V개의 줄에 걸쳐 i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력.
• 시작점은 0으로 출력. 경로가 없으면 INF를 출력.

조건 :

• 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하라.(간선의 가중치는 10 이하의 자연수)

---

노드의 시작 1에서부터..
만약 5개라고 한다면 1, 2, 3, 4, 5

INF에 최댓값을 지정해 놓은 변수가 필요.

플로이드 워셜 같은 느낌이 편하겠지만 시간 복잡도가 문제.
비용을 중심으로 정렬을 한 후에.

하.... 매번 구조는 똑같이 짜는데 런타임 에러만 뒤지게 때려 맞네....

import sys
import heapq

inf = 100000000

v, e = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
graph = [[] for _ in range(v + 1)]
dp = [inf] * (v + 1)
heap = []


def dijkstra(start):
    dp[start] = 0
    heapq.heappush(heap, (0, start))

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

        for next_node, next_weight in graph[node]:
            total = next_weight + weight

            if total < dp[next_node]:
                dp[next_node] = total
                heapq.heappush(heap, (dp[next_node], next_node))


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

dijkstra(k)

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

초반엔 시간초과가 자주 발생 했는데. 거리의 최소를 따지기 때문에 우선순위 큐 아니면 힙을 써야 한다.