(Python) 백준 11404번 플로이드 - class 4

21 Feb 2021 in Algorithm on BOJ

[문제 링크]

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)]

# 자기 자신으로 가는 비용 0 처리
for i in range(n + 1):
    graph[i][i] = 0

# 간선 입력 정보
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

# 플로이드워셜 로직
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])

# INF인 부분 0으로 바꿔서 출력
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()