Algorithm/Baekjoon
BOJ 11404 플로이드 Python3 - 플로이드 워셜 알고리즘
Bonita SY
2023. 7. 15. 15:06
728x90
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
# 플로이드 워셜 알고리즘
import sys
input = sys.stdin.readline
n = int(input().rstrip())
m = int(input().rstrip())
INF = int(1e9)
graph = [[INF]*(n+1) for _ in range(n+1)]
for index in range(1, n+1):
graph[index][index] = 0
for _ in range(m):
a, b, c = map(int, input().rstrip().split())
if graph[a][b] != INF:
graph[a][b] = min(c, graph[a][b])
else:
graph[a][b] = c
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b] == INF:
print(0, end=" ")
else:
print(graph[a][b], end=" ")
print()
🌟🌟🌟점화식을 잊지말자!🌟🌟🌟
Dab = min(Dab, Dak + Dkb)
728x90