알고리즘/백준

[백준] 1753번 최단경로 (파이썬)

알감자 2022. 1. 5. 23:14
 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

 

코드

import heapq
import sys

inf = sys.maxsize
V,E = map(int, input().split())
k = int(input())

tree = list([] for _ in range(V+1))
destination = [inf]*(V+1)
heap = []

def dijkstra(start):
    destination[start] = 0
    heapq.heappush(heap, [0,start])
    while heap:
        w, n = heapq.heappop(heap)
        for node, distance in tree[n]:
            new_distance = w + distance
            if new_distance < destination[node]:
                destination[node] = new_distance
                heapq.heappush(heap, [new_distance, node])

for _ in range(E):
    u, v, w = map(int, input().split())
    tree[u].append([v,w])

dijkstra(k)

for i in destination[1:]:
    print(i if i != inf else "INF")
저작자표시 (새창열림)