[백준] 11404번 플로이드

플로이드-워셜 알고리즘의 전형적인 예제

마지막 출력에 길 없으면 0 출력한다 구현하는 걸 잊지 말아야한다.

채점 진짜 오래걸렸다. 5분 걸림... 왜지?

 

n = int(input())
m = int(input())
INF = int(1e9)
graph = [[INF] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

for i in range(n+1):
    for j in range(n+1):
        if i == j:
            graph[i][j] = 0

for k in range(n+1):
    for a in range(n+1):
        for b in range(n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] >= INF:
            print(0, end = " ")
        else:
            print(graph[i][j], end = " ")
    print()