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

풀이

최단 경로 알고리즘 중 하나인 플로이드 워셜 알고리즘으로 풀 수 있는 문제였습니다.

 

플로이드 워셜 알고리즘을 이해하고 있다면, 쉽게 풀 수 있는 문제였습니다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다 라는 것만 주의하시면 될 것 같습니다.

 

import sys

input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

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

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:
            print(0, end=' ')
        else:
            print(graph[i][j], end=' ')
    print()