백준 11404 플로이드

https://www.acmicpc.net/problem/11404

모든 각 정점에서 각 정점가지의 최단거리를 찾는데는 플로이드-워셜 알고리즘을 사용한다.
플로이드-워셜 알고리즘은 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하는데,
특정 노드 k를 거쳐서 방문하는 경로가 더 최단거리인지를 확인하면 된다.

import sys
import math
input = sys.stdin.readline
n = int(input())
m = int(input())
dp = [[math.inf]*n for i in range(n)]
for i in range(m):
    a,b,c = list(map(int,input().split()))
    if dp[a-1][b-1] != math.inf:
        dp[a-1][b-1] = min(dp[a-1][b-1], c)
    else:
        dp[a-1][b-1] = c
for i in range(n):
    dp[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
for i in range(n):
    for j in range(n):
        if dp[i][j] == math.inf:
            dp[i][j] = 0

for row in dp:
    print(*row)