백준 1753 파이썬 python : 최단경로 @@황소처럼 우직하게@@

다익스트라는

Greedy 와 BFS 를 섞은 느낌이다

BFS에서 대신 q를 쓸 때, min heap q를 사용한다.

그래야 다음으로 가장 짧은 노드를 빠르게 찾을 수 있으니.

import sys
import heapq
inpu = sys.stdin.readline
INF = 999999999

def dijkstra(v, start, g):
    dist = [INF] * (V + 1)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        cost, loc = heapq.heappop(q)
        for l, c in g[loc]:
            c += cost
            if c < dist[l]:
                dist[l] = c
                heapq.heappush(q, [c, l])
    return dist[1:]


V, E = map(int, inpu().split())
K = int(inpu())
G = [[] for i in range(V + 1)]
for i in range(E):
    u, v, w = map(int, inpu().split())
    G[u].append([v, w])

for x in dijkstra(V, K, G):
    print(x if x != INF else "INF")

기존 백준(DFS와 BFS) 와 다른점은

다음 노드를 찾을 때, 가장 짧은 거리 노드를 찾는 것이다. 뭐 일종의 bfs지 뭐..

가장 짧은 거리 노드를 빨리 찾기 위해 heapq 를 사용하는 것이다.