백준 11404 - 플로이드
문제
https://www.acmicpc.net/problem/11404
섬 = 노드, 버스 = 간선 형태의 그래프로 저장한다. 각 노드에서 모든 노드까지의 최소 비용을 구하는 문제이다. 플로이드-워셜 알고리즘을 이용하여 풀이.
- 플로이드-워셜 알고리즘
- 각 노드에서 모든 노드까지의 최단 경로를 구하는 알고리즘.
여기서는 단순히 비용만 구한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = int(input())
m = int(input())
cost = [ [999999999 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
s, e, c = map(int, input().split())
cost[s][e] = min(cost[s][e], c)
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
cost[i][j] = 0
else:
cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
for row in cost[1:]:
for col in row[1:]:
print(col if col != 999999999 else 0, end=' ')
print()