문제

문제 링크 : https://www.acmicpc.net/problem/11404

풀이

제목에서 알 수 있는 것처럼 플로이드-워셜 알고리즘을 사용해서 풀 수 있는 문제이다.

정석적인 플로이드-워셜 알고리즘을 구현하면 풀 수 있는 문제이다.

다만 문제의 출력 설명 부분에 '만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.' 라는 구절이 있는데 이것만 신경써서 구현하면 된다.

import sys
input = sys.stdin.readline
INF = int(1e9)

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

distance = [[INF for i in range(n + 1)] for j in range(n + 1)]

for i in range(1,n+1):
    distance[i][i] = 0

for i in range(m):
    a,b,c = map(int,input().split())
    distance[a][b] = min(c, distance[a][b])

for i in range(1,n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            distance[j][k] = min(distance[j][k],distance[j][i] + distance[i][k])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if distance[i][j] != INF:
            print(distance[i][j],end = ' ')
        else:
            print(0,end=' ')
    print()