[snippet] floyd-warshall.py

백준 11404번. 플로이드에 대한 풀이를 Floyd-Warshall Algorithm의 스니펫 느낌으로 작성.

• 모든 정점에서 모든 정점까지의 Shortest Path(최단 경로) 를 구할 때 사용.
  (단, 가중치는 모두 양수여야 함.)

import sys
input = lambda: sys.stdin.readline().rstrip()
INF = int(1e9)

V = int(input())
E = int(input())
graph = [[INF]*(V+1) for _ in range(V+1)] # 1-indexed, 2D

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

for _ in range(E):
    a, b, cost = map(int, input().split())
    graph[a][b] = min(graph[a][b], cost)

#######################

for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

#######################

for i in range(1, V+1):
    for j in range(1, V+1):
        if graph[i][j] == INF:
            graph[i][j] = 0
            
for i in range(1, V+1):
    print(*graph[i][1:])