結果
問題 | No.2712 Play more! |
ユーザー |
![]() |
提出日時 | 2024-04-02 00:41:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 609 ms / 2,000 ms |
コード長 | 1,362 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 78,096 KB |
最終ジャッジ日時 | 2024-09-30 23:55:04 |
合計ジャッジ時間 | 7,587 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
inf = float('inf')class BellmanFord():def __init__(self, N):self.N = Nself.edges = []def add(self, u, v, d, directed=False):"""u = from, v = to, d = costdirected = Trueのとき、有向グラフである。"""if directed is False:self.edges.append([u, v, d])self.edges.append([v, u, d])else:self.edges.append([u, v, d])def BellmanFord_search(self, start):""":param s: 始点:return: d[i] 始点sから各点iまでの最短経路"""# infならたどり着けず# -infなら"通りたいパスに"負の閉路が存在するD = [inf for i in range(self.N)]D[start] = 0for i in range(self.N*2):for u,v,d in self.edges:if D[v] > D[u] + d:D[v] = D[u] + d#2巡目負経路が存在する場合の動きif i>=self.N:D[v]=-infreturn DN,M = map(int, input().split())A = list(map(int, input().split()))ABC = [list(map(int, input().split())) for _ in range(M)]G = BellmanFord(N)for a,b,c in ABC:G.add(a-1,b-1,c-A[b-1],True)ANS = G.BellmanFord_search(0)if ANS[N-1]==-inf:print('inf')else:print(-ANS[N-1]+A[0])