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

백준 - 1753 최단경로

풀이

다익스트라 구현

• 우선순위 큐 사용 -> 최단경로여야 하기 때문

코드

from sys import stdin, maxsize
from heapq import heappop, heappush

V, E = map(int, stdin.readline().split())
start = int(stdin.readline())
graph = [[] for _ in range(V + 1)]

INF = maxsize
distance = [INF] * (V + 1)

def dijkstra(s):
    heap = []
    distance[s] = 0
    heappush(heap, (0, s))
    while heap:
        dist, now = heappop(heap)
        # dist가 최단거리 테이블에 저장된 것보다 크면 최단경로 x -> continue로 무시
        if dist > distance[now]:
            continue
        # now와 인접한 정점들 순회하며 최단거리 저장
        for v, w in graph[now]:
            cost = dist + w
            if cost < distance[v]:
                distance[v] = cost
                # cost를 기준으로 우선순위 큐를 만들어줌(오름차순)
                heappush(heap, (cost, v))

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

dijkstra(start)

for i in distance[1:]:
    print('INF') if i == INF else print(i)