白駿11404
質問する
りゅうたい
白駿11404
に答える
これはフロイドとシエル問題の基本です.
アルゴリズムの説明をスキップします.
基本を覚える
フロイドとシエルの基本的な核心はすべての頂点の最短距離を求めることだ.
したがって,すべての頂点においてすべての頂点の最短距離を求める問題が発生した場合,このアルゴリズムを用いることができる.
基本アルゴリズムも本当に本当に本当に本当に簡単です.
pythonをベースに、for文3をネストするだけです.
どうですか.本当に簡単ですよね?
for i in range(n):
for j in range(n):
for k in range(n):
arr[j][k]=min(arr[j][k],arr[j][i]+arr[i][k])
# 플로이드 기본문제
import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
# n개의 도시의 경로를 전부 무한대 으로 초기화
city=[[10000000 for _ in range(n)] for _ in range(n)]
for i in range(m):
c1,c2,value=map(int,input().split())
city[c1-1][c2-1]=min(city[c1-1][c2-1],value)
for i in range(n):
city[i][i]=0
for i in range(n):
for j in range(n):
for k in range(n):
city[j][k]=min(city[j][k],city[j][i]+city[i][k])
for i in city:
for j in i:
if j==10000000:
j=0
print(j,end=' ')
print()
最初のタイムアウト
import sys
input=sys.stdin.readline
この部分をやらないと、Pythonがタイムアウトすることがあります.常に追加結果は正しい
Reference
この問題について(白駿11404), 我々は、より多くの情報をここで見つけました https://velog.io/@chuneeeee/백준-11404-파이썬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol