[BOJ] 11404. 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

 

문제: 모든 도시에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하라.

 

문제 이해하기!!

모든 도시로 가는 최소 비용을 구하면 되는 문제입니다.

한 루트의 최소비용을 구할 때는 다익스트라를 쓰지만,

모든 곳의 최소비용을 구할 때는 플로이드 와샬을 쓰면 됩니다.

다만 주의할 점은 정점의 갯수 ** 3 이므로 정점의 갯수가 작을 때 쓸 수 있습니다.

 

그래서 푼 방법은

1. 처음 받는 루트와 비용을 최소값으로 2차원 배열에 넣어 줍니다.

2. 3중 for문을 사용하여 시작, 환승, 도착 지점을 활용하여 해당 지점의 최소 비용을 찾아줍니다.

3. 갈 수 없는 곳은 0으로 표시하여 주고 출력합니다.

 

마지막 0으로 표시하는 부분을 빠뜨리면 틀릴 수 있으니까 조심하시면 됩니다!

(내가 저걸로.. 2번이나 틀렸다고... ㅠㅠ)

 

코드:

from collections import defaultdict
from heapq import *
from sys import stdin
input = stdin.readline


N = int(input())
M = int(input())
ans = [[float("inf")] * N for _ in range(N)]

for _ in range(M):
    start, end, cost = map(int, input().split())
    ans[start-1][end-1] = min(ans[start-1][end-1], cost)

for _ in range(N):
    ans[_][_] = 0

for i in range(N):
    for j in range(N):
        for k in range(N):
            ans[j][k] = min(ans[j][i] + ans[i][k], ans[j][k])

for i in range(N):
    for j in range(N):
        if ans[i][j] == float('inf'):
            ans[i][j] = 0

for i in range(N):
    print(*ans[i])