플로이드 - 11404번

동적 계획법 방식의 플로이드 워셜 알고리즘을 사용하는 문제이다.

그래프의 모든 정점에서 다른 정점들 까지의 최소 비용을 구해야한다.

갈 수 없는 곳은 math 모듈의 inf 무한대를 사용하여 표현해주고 마지막에 출력할 때 0으로 바꿔준다.

원본 그래프를 손상시키지 않기 위해 deepcopy를 사용했다.

import sys
from copy import deepcopy
from math import inf
n = int(input())
m = int(input())
graph = [[inf]*(n) for _ in range(n)]
for i in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    if graph[a-1][b-1]==inf:
        graph[a-1][b-1] = c
    else:
        graph[a-1][b-1] = min(graph[a-1][b-1],c)
for i in range(n):
    for j in range(n):
        if i==j:
            graph[i][j]=0

def floyd(graph):
    d = deepcopy(graph)

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

d = floyd(graph)
for i in range(n):
    for j in range(n):
        if d[i][j] == inf:
            # print(i,j,d[i][j])
            d[i][j] = 0
        print(d[i][j],end=' ')
    print()