플로이드

백준 11404번: 플로이드

아이디어

N * N 사이즈의 배열에 비용을 저장한다. (r, c)에는 r번 노드에서 c번 노드까지 가는데 드는 비용이 담겨 있다.
(1, 1)부터 (N, N)까지 탐색하면서, i번째 노드를 거쳐서 갈 때 비용이 더 작으면 업데이트한다.

3중 반복문을 사용하는데, 이 때 최상단 반복문에서 몇 번째 노드를 거쳐갈지 정해줘야 한다.

코드

import sys
input = sys.stdin.readline
INF = 987654321
N = int(input())
M = int(input())

dist = [[INF] * (N + 1) for _ in range(N + 1)]

for idx in range(N + 1):
    dist[idx][idx] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    dist[a][b] = min(dist[a][b], c)

for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            # j -> k vs j -> i -> k 뭐가 더 빠를까?
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

for r in range(1, N + 1):
    for c in range(1, N + 1):
        if dist[r][c] == INF:
            print(0, end=' ')
        else:
            print(dist[r][c], end=' ')
    print()

여담

반복문 순서 주의