[白俊]1389号-(Python Python)-floyd-Warshall
1102 ワード
質問リンク:https://www.acmicpc.net/problem/1389
この問題もFloydとShallアルゴリズムで解決した.
人ではなく、前から多くの都市や橋が放たれていると思って、すぐに理解できます.
各最短パスを求め、パスマージ時に最小の人を出力すればよい.
この問題もFloydとShallアルゴリズムで解決した.
人ではなく、前から多くの都市や橋が放たれていると思って、すぐに理解できます.
各最短パスを求め、パスマージ時に最小の人を出力すればよい.
import sys
input = sys.stdin.readline
inf = sys.maxsize
n, m = map(int, input().split())
graph =[[inf] * n for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
graph[a-1][b-1] = 1
graph[b-1][a-1] = 1
for k in range(n):
for i in range(n):
for j in range(n):
if i == j:
graph[i][j] = 0
elif graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
sum = [0] * n
ans = inf
for i in range(n):
for j in range(n):
sum[i] += graph[i][j]
if ans > sum[i]:
ans = sum[i]
result = i
print(result + 1)
Reference
この問題について([白俊]1389号-(Python Python)-floyd-Warshall), 我々は、より多くの情報をここで見つけました https://velog.io/@hamfan524/백준-1389번-Python-파이썬-Floyd-Warshallテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol