BOJ 11404 플로이드 Python3 - 플로이드 워셜 알고리즘

 

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

11404번: 플로이드

 

 

 

 

# 플로이드 워셜 알고리즘
import sys
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
INF = int(1e9)
graph = [[INF]*(n+1) for _ in range(n+1)]
for index in range(1, n+1):
    graph[index][index] = 0

for _ in range(m):
    a, b, c = map(int, input().rstrip().split())
    if graph[a][b] != INF:
        graph[a][b] = min(c, graph[a][b])
    else:
        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])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print(0, end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

 

🌟🌟🌟점화식을 잊지말자!🌟🌟🌟

Dab = min(Dab, Dak + Dkb)