백준 11404 플로이드

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

 

 이 문제는 말 그대로 플로이드 워셜 알고리즘을 구현하는 문제이다.

 

플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점으로 향하는 최단거리를 구할 때 사용한다. 이 알고리즘은 중간으로 경유하는 점들을 하나하나 검사해, 시작과 끝의 최단거리를 구한다. 그렇기에 시간복잡도는 O(n^3)이다. 

 

 이 때 유의할 점이, 가장 바깥쪽의 for문에는 중간 경유하는 점을 넣어야 한단 점이다. 만약 그렇지 않다면, 완벽히 계산되지 않은채로, 어느 정점에서는 시작과 끝이 끝나버리고, 새로운 최단거리가 발견되어도 갱신하지 못하기 때문이다. 그렇기에 시작과 끝의 계산을 최대한 뒤로 미루어서 항상 갱신할 수 있도록 해야한다.

 

import sys
input = sys.stdin.readline
import math

nodes = int(input().rstrip())
edges = int(input().rstrip())

d=[[math.inf for a in range(nodes+1)] for b in range(nodes+1)]
for _ in range(edges):
    a,b,c = map(int,input().rstrip().split())
    d[a][b]=min(d[a][b],c)

for a in range(1,nodes+1):
    d[a][a]=0


for mid in range(1,nodes+1):
    for start in range(1,nodes+1):
        for end in range(1,nodes+1):
            d[start][end] = min(d[start][end],d[start][mid]+d[mid][end])

for a in d[1:]:
    for b in a[1:]:
        if b==math.inf:
            print(0,end=' ')
        else:
            print(b,end=' ')
    print()