O(ElgE)의 시간복잡도로 모든 정점까지 그래프 최단경로를 찾아야한다.
힙을 이용한 최소비용의 경로를 우선순위로 연산하여 노드가 2만개까지 대량으로 주어줘도 빠르게 찾을 수 있도록 목표를 잡았다.
bfs알고리즘과 기본흐름이 유사하다. 각 노드의 최소비용 리스트를 무한(매우 큰 수)로 초기화하고 힙에 들어가는 원소들은 노드의 비용과 번호를 넣도록한다. while 반복문 안에서는 현재 처리중인 노드와 연결된 노드에 대해 (현재 노드 비용 + 그 노드 비용)이 먼저 선언한 최소비용 리스트의 그 노드의 비용보다 작다면 갱신하고 힙에 새롭게 갱신된 그 노드의 비용, 그 노드의 번호 순으로 넣어주고 반복한다. 최소비용 리스트가 완성되었다면 문제에서 요구한 양식대로 출력하도록한다.
import heapq,sys
v,e = [*map(int, sys.stdin.readline().split(' '))]
start = int(sys.stdin.readline())
info = dict()
for i in range(e):
point1, point2, cost = [*map(int, sys.stdin.readline().split(' '))]
if point1 in info:
info[point1] += [(point2,cost)]
else:
info[point1] = [(point2,cost)]
hq = [(0,start)]
inf = 2**99
d = [inf for _ in range(20001)]
d[start] = 0
while hq:
cost,curr = heapq.heappop(hq)
if d[curr] != cost:
continue
if curr not in info:
continue
for nxt,nxtCost in info[curr]:
if d[curr] + nxtCost >= d[nxt]:
continue
d[nxt] = d[curr] + nxtCost
heapq.heappush(hq, (d[nxt], nxt))
for i in range(1, v + 1):
print(d[i] if d[i] != inf else 'INF')