프로그래밍/Python
[Python] 백준 11404 플로이드
모영이
2021. 2. 16. 17:23
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
플로이드 와샬 알고리즘
1) i 에서 j 까지의 최단 거리를 (i ~ k + k ~ j)와 비교하며 업데이트
2) INF 값 그대로면 0출력, 아닐시 거리 값 출력
전체 코드
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
INF = sys.maxsize
dosi = [[INF for _ in range(N+1)] for __ in range(N+1)]
for _ in range(M):
a, b, c = map(int, input().split())
dosi[a][b] = min(c, dosi[a][b])
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
if i == j:
dosi[i][j] = 0
else:
dosi[i][j] = min(dosi[i][j], dosi[i][k] + dosi[k][j])
for i in range(1, N + 1):
for j in range(1, N + 1):
if dosi[i][j] == INF:
print(0, end = ' ')
else:
print(dosi[i][j], end = ' ')
print()