백준 1753 최단경로

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)