Algorithm/Baekjoon
[백준] 11404 : 플로이드 - Python
Dev.sohee
2020. 7. 10. 00:51
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 �
www.acmicpc.net
import sys
# Inf의 범위가 작으면 틀릴 수 있으니 주의!!
Inf = 100000000
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
d = [[Inf] * n for _ in range(n)]
for i in range(m):
a, b, c = map(int, sys.stdin.readline().split())
if d[a-1][b-1] > c:
d[a-1][b-1] = c
for k in range(n):
for i in range(n):
for j in range(n):
# 자기 자신으로 오는 경우
if j == i:
d[i][j] = 0
# k를 거쳐서 가는 것, 원래 값 중 최소 값
else:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
for i in range(n):
for j in range(n):
if d[i][j] == Inf:
print(0, end = ' ')
else:
print(d[i][j], end = ' ')
print()