백준 / 골드 4 / 1753 최단경로 / Python [다익스트라, 방향그래프]

우선순위 큐

값이 작거나 큰 순으로 값을 반환하는 큐
주로 최소힙/최대힙으로 구현한다.

Python의 import heapq

최소힙으로 구현되어있다. O(log2N)의 삽입 속도, O(1)의 반환 속도

https://docs.python.org/ko/3/library/heapq.html

import heapq
q = [] 
# heapq.heapify(q) 제자리 변환, O(N)


heapq.heappush(q, value)
v = heapq.heappop(q)

풀이

heap에 key를 weight, destination을 담을 때, weight를 먼저 담아야 거리 순으로 최소힙에서 반환해준다.

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxvalue

V, E = map(int, input().split())
K = int(input())

mini_sum = [INF] * (V+1)
graph = [[] * (V+1)]
heap = []

'''
graph[1] = [(2, 2), (3, 3)]..
graph[2] = [(4, 3), (5, 4)]
graph[3] = [(6, 4)]
graph[4] = []
graph[5] = [(1, 1)]

힙에 시작정점 넣고,
최단거리의 정점 u를 뽑아.
이미 찾은 다른 길이 더 빠르면 넘어가.
u의 인접 정점 v 순회하면서
더 빠른 길이면 업데이트 하고, 전파해야되니까 힙에 넣어

'''
def dijkstra(start):
    heapq.heappush(heap, (0, start))
    
    mini_sum[start] = 0
    
    while heap:
        wsum, u = heapq.heappop(heap)
        
        if mini_sum[u] < wsum:
            continue
        
        for w, v in graph[u]:
            if wsum + w < mini_sum[u]:
                mini_sum[u] = wsum + w
                heapq.heappush(heap, (w + sum, v))
        
    
    
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((w, v))
    
dijkstra(K)

for i in range(1, V+1):
    print('INF' if mini_sum[i] == INF else mini_sum[i])