문제

풀이

문제에서의 핵심은 결국 그래프의 정보를 입력받고 주어진 start 노드에서 다른 지점까지의
최단경로의 값을 출력해주면 된다.

위 문제에서 캐치할 정보는 주어지는 그래프가 방향그래프이다만 인지하고 다잌스트라알고리즘을
그대로 이용해주면 풀리는 문제이다

코드

# input sample
# 5 6
# 1
# 5 1 1
# 1 2 2
# 1 3 3
# 2 3 4
# 2 4 5
# 3 4 6

# output sample
# 0
# 2
# 3
# 7
# INF

# 입력 : 첫째줄에 정점의 개수 V와 간선의 개수 E가 주어진다.
# 	    둘째줄에는 시작노드의 번호가 주어진다
#       셋째줄부터는 세개의 정수 u, v, w가 주어지는데
#       이는 시작노드 도착노드 가중치값을 나타낸다.
#       위 그래프는 방향 그래프이다.

import sys
import heapq

INF = int(1e9)

input = sys.stdin.readline

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

start = int(input().rstrip())

graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1)

for _ in range(E):
  u, v, w = map(int , input().split())
  graph[u].append((w,v))

def dijakstra(start):

  q = []

  heapq.heappush(q, (0, start))
  distance[start] = 0
  
  while q:
    dis, cur = heapq.heappop(q)

    if(dis > distance[cur]):
      continue

    for j in graph[cur]:
      cost = dis + j[0]
      if(cost < distance[j[1]]):
        distance[j[1]] = cost
        heapq.heappush(q, (cost, j[1]))
    
dijakstra(start)

for i in range(1, V+1):
  if(distance[i] == INF):
    print('INF')
  else:
    print(distance[i])