結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2021-04-05 10:11:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 157 ms / 5,000 ms |
コード長 | 609 bytes |
コンパイル時間 | 480 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 76,880 KB |
最終ジャッジ日時 | 2024-12-30 12:24:13 |
合計ジャッジ時間 | 5,453 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
from heapq import heappop, heappush n = int(input()) c = int(input()) v = int(input()) L = [list(map(int,input().split())) for i in range(4)] e = [[] for i in range(n)] for s,t,y,m in zip(L[0],L[1],L[2],L[3]): e[s-1].append((t-1,y,m)) inf = 10**10 dis = [[inf]*(c+1) for i in range(n)] dis[0][c] = 0 q = [(0,0,c)] while q: time,now,d = heappop(q) if time > dis[now][d]: continue for nex,y,m in e[now]: if d >= y and dis[nex][d-y] > time+m: dis[nex][d-y] = time+m heappush(q, (time+m,nex,d-y)) ans = min(dis[-1]) if ans == inf: ans = -1 print(ans)