アルゴリズム|白駿1956.スポーツ(Python)

6749 ワード

自由戦争サイクルグラフ＃グラフ＃アルゴリズム#アルゴリズム# algorithm テキストリンク

本題の著作権はBAEKJOON
白駿1956。モーションリンク

質問する

Vの村とEの道路からなる都市があります.道は村と村の間にあり、一方通行です.村のコンビニ1番からV番まで番号があります.
道路に沿ってトレーニングの道を見つけたいです.運動後はスタート地点に戻ったほうがいいので、周期を見つけたいです.しかし、あなたは運動が嫌いなので、道の長さの和を最小にしたいと思っています.
道路情報を取得する場合は、道路の長さの和の最小周期を検索するプログラムを作成します.2つの村を往復する場合も自転車に含めて注意が必要です.

入力

最初の行では、VとEはスペースを隔てています.(2≦V≦400,0≦E≦V(V−1)),次のE行はそれぞれ3つの整数a,b,cを与える.これは、a番村からb番村までの距離がcの道路があることを意味します.(注意a→b)距離は10000以下の自然数です.(a,b)同じ道を何度も交わらない.

しゅつりょく

1行目に最小サイクル道路長の和を出力します.モーションパスが見つからない場合は、-1を出力します.

コード#コード#

import sys

V, E = map(int, input().split())

INF = sys.maxsize
arr = [[INF] * V for _ in range(V)]

for _ in range(E):
    a, b, c = map(int, input().split())
    arr[a-1][b-1] = c

for k in range(V):
    for i in range(V):
        for j in range(V):
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

ans = INF
for i in range(V):
    ans = min(ans, arr[i][i])

if ans == INF:
    print(-1)
else:
    print(ans)