https://www.acmicpc.net/problem/11404
시간 1초, 메모리 256MB
input :
- n (2 ≤ n ≤ 100)
- m(1 ≤ m ≤ 100,000)
- a b c(시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수)
output :
- n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력
조건 :
- 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
문제의 이름과 같이 모든 도시에서 모든 도시로 이동하는 방법을 물어보기 때문에 플로이드 와샬 알고리즘을 사용해야 한다.
플로이드 와샬 알고리즘이 왜 수행이 가능한가? 순서가 존재한다면 먼저 하는 것에 차이가 존재할 텐데 말이다.
어떤 최단경로가
1 - 3 - 5 - 4 - 2로 이루어진다고 할 때.
우리는 특정 k를 통해서 가는 경우를 체크 할 수 있다.
맨 처음에는 1 - 2 로만 가는 걸로 저장을 해두지만
k가 3일 때 1 - 3 - 5를 찾고
k 가 4일 떄 5 - 4 - 2를 찾고 마지막에는 1 - 5 - 2를 찾게 되면 모든 경우를 확인 할 수 있다.
맨 처음에는 아니 1 - 2 에서 어떻게 노드를 거쳐가는 걸 확인한다고는 하지만 그렇게 하면 그냥 노드 3개가 연결되는 거 아니냐 라고 생각을 했었는데 그렇지 않았다.
암튼 맨 처음에는 모든 위치에 inf를 저장하고, 자기 자신에게는 0을 저장해둔다.
그 이후 모든 경우의 수에 대해 k를 거쳐가는 경우에는 어떻게 되는 지를 확인하며 업데이트를 하도록 하자.
이를 통해 모든 경우를 확인할 수 있다.
import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
edge = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().split())
edge[a - 1][b - 1] = min(edge[a - 1][b - 1], c)
for i in range(n):
edge[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j])
for i in range(n):
for j in range(n):
if edge[i][j] == float('inf'):
edge[i][j] = 0
for i in range(n):
print(*edge[i])
