[백준][Python] 1753번 최단경로 - 그래프, 최소힙

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

1753번: 최단경로

 

 

Python

import heapq
import sys
input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())
graph = [[] for _ in range(v+1)]
visit = [0] * (v+1)
dist = ["INF"] * (v+1)

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))


def di(start):  # 최소 힙으로 빠르게 가장 작은 노드 찾기
    global visit, dist
    hq = []
    heapq.heappush(hq, (0, start))
    dist[start] = 0
    now = start
    while hq:
        d, now = heapq.heappop(hq)
        if dist[now] >= d:
            for i in graph[now]:
                if dist[i[0]] == "INF" or dist[i[0]] > d+i[1]:
                    dist[i[0]] = d+i[1]
                    heapq.heappush(hq, (dist[i[0]], i[0]))


di(k)
print("\n".join(map(str, dist[1:])))

 

 

+) heapq 라이브러리

https://wakaranaiyo.tistory.com/247

[Python] heapq 라이브러리 살펴보기