[백준] #11404 Python 플로이드 워셜

https://www.acmicpc.net/problem/11404

하 처음에 자기 자신으로 가는 i == j 의 경우를 0으로 초기화안해서 요상하게 나왔다..

이게 아직도 플로이드 워셜의 알고리즘이 완전히 확 와닿지는 않네

중간에 거쳐가는 노드의 순서는 알고리즘에 영향이 없는건가?

뒤에서 더 적은 비용으로 바뀐 걸 앞에서 다시 적용할 수 없는거잖아... 내 수학 머리..ㅠ

아 어차피 중간경유한 순서는 더하기만 하는거고 차피 전체 다 훝으니까 되는 거 같다. 이게 와닿을랑 말랑 한다

무한은 1e9로 설정해주었다

import sys
input = sys.stdin.readline

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

bus_map = [[INF] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            bus_map[i][j] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    bus_map[a - 1][b - 1] = min(bus_map[a - 1][b - 1], c)

def Floyd(bus_map, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                bus_map[i][j] = min(bus_map[i][j], bus_map[i][k] + bus_map[k][j])

Floyd(bus_map, n)

for el in bus_map:
    for i in el:
        if i >= INF:
            print(0, end = ' ')
        else: print(i, end = ' ')
    print()