結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2023-09-27 07:22:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 184 ms / 5,000 ms |
コード長 | 851 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 79,036 KB |
最終ジャッジ日時 | 2024-07-20 01:31:00 |
合計ジャッジ時間 | 5,290 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
from collections import defaultdict from heapq import heappop, heappush 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 = defaultdict(list) for i in range(v): s, t, y, m = S[i], T[i], Y[i], M[i] s -= 1 t -= 1 G[s].append((t, y, m)) INF = 10**18 DP = [[INF for _ in range(c + 1)] for _ in range(n)] DP[0][0] = 0 H = [(0, 0, 0)] while H: cp, cc, ct = heappop(H) if ct > DP[cp][cc]: continue for np, dc, dt in G[cp]: nc = cc + dc nt = ct + dt if nc > c: continue if nt >= DP[np][nc]: continue DP[np][nc] = nt heappush(H, (np, nc, nt)) ans = min(DP[n - 1]) if ans == INF: ans = -1 print(ans)