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

1753번: 최단경로

---

우선순위큐에 다익스트라 알고리즘을 사용한다

v_arr: 최단경로 저장

arr: 간선 저장

heap: 계산할 것들 저장

1. heap(우선순위 큐)에 [0, 시작점]을 넣는다.
2. 시작점에 연결되있는 것들을 v_arr와 비교한 뒤에 더 작다면 v_arr를 수정하고, heap에 넣어줌
3. 반복 계산
4. v_arr 출력

 

import sys
import heapq
 
input = sys.stdin.readline
V, E = map(int, input().split())
arr = [[] for _ in range(V+1)]
start = int(input())
heap = [[0, start]]
v_arr = [sys.maxsize]*(V+1)
v_arr[start] = 0
 
for _ in range(E):
    start, end, w = map(int, input().split())
    arr[start].append([end, w])
 
while heap:
    value, v = heapq.heappop(heap)
    for n, w in arr[v]:
        if v_arr[n] > value+w:
            v_arr[n] = value+w
            heapq.heappush(heap, [value+w, n])
 
for i in range(1, V+1):
    if v_arr[i] == sys.maxsize:
        print("INF")
    else:
        print(v_arr[i])