[백준] 1753번 최단경로 (Python)

백준 1753 최단경로

흔한 유형이지만 큐를 활용하는 과정에서 실수했던 문제다. 최단 경로를 찾는 문제는 다익스트라 알고리즘을 많이 활용한다. 나는 우선순위 큐를 사용하여 문제를 해결했다. 이 문제의 포인트는 이와 같다.

1. 우선순위 큐를 활용하기 때문에 dp에 저장된 값을 비교할 필요가 없다.
2. dp에 값이 입력되어 있다면 무시한다.

import sys
from queue import PriorityQueue

v, e = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline().strip())
edges = [{} for _ in range(v + 1)]
dp = [-1 for _ in range(v + 1)]
pq = PriorityQueue()

for _ in range(e):
    a, b, w = map(int, sys.stdin.readline().split())
    if b in edges[a].keys():
        edges[a][b] = min(edges[a][b], w)
    else:
        edges[a][b] = w

pq.put([0, start])

while not pq.empty():
    c, p = pq.get()
    if dp[p] == -1:
        dp[p] = c
        for edge, cost in edges[p].items():
            pq.put([c + cost, edge])

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