[백준] 11404번: 플로이드

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

initial

It is just the typical floyd warshall template. Nothing tricky except maybe when getting inputs of costs from city a to b, we double check if that cost value is indeed the minimum cost to travel that way via:

for _ in range(m):
    a, b, c =  map(int, sys.stdin.readline().split())
    ## not just graph[a][b] = c
    graph[a][b] = min(c, graph[a][b])

Also, for this question, reverse travel is not allowed so no graph[b][a] = c.

solution

import sys 
n = int(input())
m = int(input())
inf = float('inf')

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

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

for _ in range(m):
    a, b, c =  map(int, sys.stdin.readline().split())
    graph[a][b] = min(c, graph[a][b])


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

for row in graph[1:]:
    print(" ".join(map(str, row[1:])))