[백준] 11404번 플로이드 - 파이썬

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

11404번: 플로이드

풀이

플로이드와셜 알고리즘을 사용한다. 문제에서 출발지와 도착지가 같지만 비용이 다른 노선이 있기에 최소비용 노선을 골라서 2차원 리스트에 넣어주어야한다.

# 11404번 플로이드
import sys
input = sys.stdin.readline
INF = sys.maxsize

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

출력결과