結果
問題 | No.2712 Play more! |
ユーザー |
|
提出日時 | 2024-03-31 15:28:06 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 609 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 78,572 KB |
最終ジャッジ日時 | 2024-09-30 20:43:46 |
合計ジャッジ時間 | 4,117 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | AC * 3 RE * 30 |
ソースコード
from heapq import * N, M = map(int, input().split()) A = list(map(int, input().split())) g = [] for _ in range(M): a, b, c = map(int, input().split()) a -= 1 b -= 1 g.append((a, b, c)) assert(N == 5) inf = 10 ** 20 dist = [-inf] * N dist[0] = 0 for i in range(2 * N): for u, v, c in g: if dist[u] != -inf and dist[v] < dist[u] + A[v] - c: dist[v] = dist[u] + A[v] - c now_dist = dist[:] for i in range(2 * N): for u, v, c in g: if dist[u] != -inf and dist[v] < dist[u] + A[v] - c: dist[v] = dist[u] + A[v] - c if now_dist[N - 1] < dist[N - 1]: exit(print("inf")) print(dist[N - 1] + A[0])