[Algorithm] 11404 플로이드 워셜

n=int(input())
m=int(input())
INF=int(1e9)

graph=[[INF] * (n+1) for _ in range (n+1)]

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

for _ in range (m):
    a,b,c=map(int,input().split())
    if graph[a][b]>c:
        graph[a][b]=c


for k in range (1,n+1):
    for a in range (1,n+1):
        for b in range (1,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()

플로이드 워셜은
graph[a][b]=min(graph[a][b], graph[a][k]+graph[k][b])
이 점화식만 이해한다면 구현하기가 쉽다.
a -> b로 가는 거리를 a에서 b로 바로가는 루트 1과 a에서 어떤 노드를 거쳐 b로 가는 루트 2를 비교해 최단경로를 구하는 것이다.