설명

그래프가 주어지고 출발노드가 주어졌을때, 출발노드에서 모든 노드로가능 최단경로를 나타내주는
알고리즘이다.

입력은 그래프에 대한정보 vector와 edge에 대한 정보를 입력받고
출력은 각 vector를 가기위한 최소비용을 출력해준다.

방식

(여기서 말하는 테이블을 최종적으로 각 노드마다의 가는 최소비용을 저장한다.)
1.시작노드를 설정한다.
2.시작노드에서 갈 수 있는 노드를 찾고 그 노드들의 가는 비용이 현재 테이블에
있는 비용보다 작다면 테이블을 갱신해준다.
3.방문할 수 있는 노드중 비용이 제일 작은 노드를 방문해준다.
4.방문한 노드에서 방문할 수 있는 노드들을 가는 비용이 현재 테이블에 있는 비용보다 작다면
테이블을 갱신한다.
5.모든 노드를 방문 할 때까지 3번 4번을 반복해준다.

코드

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

#입력예시
# 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
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):
  visit[start] = True
  table[start] = 0
  visit[0] = True
  
  for i in graph[start]:
    if(table[i[0]] > i[1]):
      table[i[0]] = i[1]

  for i in range(V-1):
    next = getMinVector()
    visit[next] = True
    
    for j in graph[next]:
      cost = table[next] + j[1]

      if(cost < table[j[0]]):
        table[j[0]] = cost

    
def getMinVector():
  min = INF
  minIndex = 0
  for i in range(1, V+1):
    if(table[i] < min and visit[i] == False):
      min = table[i]
      minIndex = i

  return minIndex
      

dijakstra(start)

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