황소개발자

다익스트라는 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 di..