import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
v, e = map(int, input().split())
start = int(input())
g = [[] for _ in range(v)]
for _ in range(e):
a, b, c = map(int, input().split())
g[a-1].append((b-1, c))
d = [INF] * v
q = []
heapq.heappush(q, (0, start-1))
d[start -1] = 0
while q:
dist, now = heapq.heappop(q)
if d[now] < dist:
continue
for i in g[now]:
cost = dist + i[1]
if cost < d[i[0]]:
d[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
for i in d:
if i == INF:
print('INF')
else:
print(i)
다익스트라로 품 (input()쓰면 파이썬 제출할 때 시간 초과남, 입력이 몇만줄을 넘어가서 sys.stdin.readline으로 시간 줄이기 가능)
INF = int(1e9)
v, e = map(int, input().split())
start = int(input())
start -= 1
g = [[INF] * v for _ in range(v)]
for i in range(v):
g[i][i] = 0
for _ in range(e):
a, b, c = map(int, input().split())
g[a-1][b-1] = c
for i in range(v):
for a in range(v):
for b in range(v):
g[a][b] = min(g[a][b], g[a][i]+g[i][b])
for i in range(v):
if g[start][i] == INF:
print('INF')
else:
print(g[start][i])
플로이드 와샬 -> 메모리/시간 초과
플로이드 : O(v^3) -> 20000^3 = 8000000000000 = 8조 = 8000초
다익스트라 : O((v+e)loge)