結果
問題 | No.1344 Typical Shortest Path Sum |
ユーザー |
![]() |
提出日時 | 2021-01-26 11:01:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 226 ms / 2,000 ms |
コード長 | 836 bytes |
コンパイル時間 | 290 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 77,172 KB |
最終ジャッジ日時 | 2024-06-23 10:24:30 |
合計ジャッジ時間 | 6,343 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#yuki-1344def bellman_ford(s, n, Edges):sp = [float('inf')]*n #各頂点への最短路sp[s] = 0 #自身への距離は0for i in range(n): #頂点の数だけ回すupdate = False #更新が行われたかfor x, y, cost in Edges:if sp[x] < float('inf') and sp[y] > sp[x] + cost:sp[y] = sp[x] + costupdate = Trueif not update:breakif i == n-1: #負閉路が存在return Falsereturn spN, M = map(int, input().split()) #N頂点、M辺#辺集合Edges = set()for _ in range(M):s, t, d = map(int, input().split())Edges.add((s-1, t-1, d))#到達不可能な場合0にする設定for i in range(N):sp = bellman_ford(i, N, Edges)print(sum(l if l < float('inf') else 0 for l in sp))