会場抽出(Floyd-Warshallアプリ)
8638 ワード
作成日:2022年2月28日午後5:43
インプリメンテーションコード
# 회장뽑기(플로이드-워샬 응용)
import sys
sys.stdin = open("in5.txt", "rt")
if __name__ == "__main__":
n = int(input())
dis = [[5000 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
dis[i][i] = 0
while True:
a, b = map(int, input().split())
if a == -1 and b == -1:
break
dis[a][b] = 1
dis[b][a] = 1
# 플로이드 워샬 알고리즘
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
res = []
for x in range(1, n+1):
res.append(max(dis[x][1:]))
minRes = min(res)
print(minRes, res.count(minRes))
for i in range(len(res)):
if res[i] == minRes:
print(i+1, end=' ')
今回の問題では,各ノード間の接続は双方向であるため,dis[a][b]=1のようにdis[b][a]=1のように双方向に値を付与する.Reference
この問題について(会場抽出(Floyd-Warshallアプリ)), 我々は、より多くの情報をここで見つけました https://velog.io/@lsj8706/회장뽑기플로이드-워샬-응용テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol