結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2022-10-15 18:48:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 126 ms / 5,000 ms |
コード長 | 748 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,196 KB |
実行使用メモリ | 77,648 KB |
最終ジャッジ日時 | 2024-06-26 20:13:26 |
合計ジャッジ時間 | 4,248 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
INF = 1 << 60 import heapq n = int(input()) c = int(input()) v = int(input()) s = list(map(int, input().split())) t = list(map(int, input().split())) y = list(map(int, input().split())) m = list(map(int, input().split())) g = [[] for _ in range(n)] for i in range(v): g[s[i] - 1].append((t[i] - 1, y[i], m[i])) dist = [[INF for _ in range(c + 1)] for _ in range(n)] dist[0][c] = 0 hp = [(0, 0, c)] while len(hp) > 0: cd, cv, cc = heapq.heappop(hp) if cd > dist[cv][cc]: continue for nv, cy, cm in g[cv]: if cc >= cy and dist[nv][cc - cy] > dist[cv][cc] + cm: dist[nv][cc - cy] = dist[cv][cc] + cm heapq.heappush(hp, (dist[nv][cc - cy], nv, cc - cy)) ans = min(dist[-1]) if ans < INF: print(ans) else: print("-1")