설명

다익스트라 알고리즘에서 시간복잡도를 힙을 이용해 줄인 알고리즘이다.

코드

#다익스트라 알고리즘 구현

#입력예시
# 6 11
# 1
# 1 2 2
# 1 3 5
# 1 4 1
# 2 3 3 
# 2 4 2
# 3 2 3
# 3 6 5
# 4 3 3
# 4 5 1
# 5 3 1
# 5 6 2

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

V, E = map(int, input().split())
start = int(input().rstrip())

graph = [[] for i in range(V+1)]
visit = [False] * (V+1)
table = [INF] * (V+1)

for i in range(E):
  a, b, c = map(int, input().split())
  graph[a].append((b,c))

def dijakstra(start):
  q = []
  heapq.heappush(q, (0, start))
  table[start] = 0
  while (q):
    dist, now = heapq.heappop(q)

    if(table[now] < dist):
      continue;

    for i in graph[now]:
      cost = dist + i[1]

      if(table[i[0]] > cost):
        table[i[0]] = cost
        heapq.heappush(q,(cost, i[0]))


dijakstra(start)

for i in range(1,V+1):
  if(table[i] == INF):
    print("INFINITY")
  else:
    print(table[i])