[Python] BOJ/백준 11404번 플로이드

[문제]

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

11404번: 플로이드

 

[풀이]

문제에도 플로이드라고 나왔지만 모든 정점에서 다른 모든 정점으로의 최단 경로를 구해야 하기 때문에 플로이드 와샬로 풀었다.

 

+ 처음에는 INF 로 안풀고 문제에 비용의 최댓값이 100,000 이라 나와있어 리스트를 100001로 초기화하고 풀었는데 틀렸다..

이유는 모르겠음 그냥 앞으로 저런 문제 나오면 int(1e9)로 풀어야지

 

 

[코드]

from sys import stdin

input = stdin.readline
n = int(input())
m = int(input())
INF = int(1e9)

route = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    start, end, cost = map(int, input().split())
    route[start][end] = min(cost, route[start][end])

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                route[i][j] = 0
            else:
                route[i][j] = min(route[i][j], route[i][k] + route[k][j])

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