백준 11404 플로이드

과정

• 플로이드 워셜
• 결과 그래프를 그대로 출력한다.

주의사항

• 경로가 여러 개가 있을 수 있다.
• 경로가 없는 경우 0을 출력한다.

import sys

sys.stdin = open("input.txt")

INF = 1e9

n = int(input())
m = int(input())

input = sys.stdin.readline

dp = [[INF for _ in range(n)] for _ in range(n)]

# 자기 자신에게 가는 것은 0
for i in range(n):
    dp[i][i] = 0

# 입력값 반영
for _ in range(m):
    a, b, c = map(int, input().split())
    dp[a - 1][b - 1] = min(dp[a - 1][b - 1], c)

# 플로이드 워셜
for k in range(n):
    for a in range(n):
        for b in range(n):
            dp[a][b] = min(dp[a][b], dp[a][k] + dp[k][b])

# 경로 없는 경우
for a in range(n):
    for b in range(n):
        if dp[a][b] >= INF:
            dp[a][b] = 0

for i in dp:
    print(*i)