結果
問題 |
No.1 道のショートカット
|
ユーザー |
![]() |
提出日時 | 2023-12-31 01:47:37 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 772 bytes |
コンパイル時間 | 491 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 294,420 KB |
最終ジャッジ日時 | 2024-09-27 16:59:52 |
合計ジャッジ時間 | 8,108 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 TLE * 1 -- * 32 |
ソースコード
n=int(input()) c=int(input()) v=int(input()) from heapq import heapify,heappop,heappush que=[] se=set() from collections import defaultdict edge=defaultdict(list) s=list(map(lambda x:int(x)-1,input().split())) t=list(map(lambda x:int(x)-1,input().split())) y=list(map(int,input().split())) m=list(map(int,input().split())) for i in range(v): si,ti,yi,mi=s[i],t[i],y[i],m[i] edge[si].append((ti,yi,mi)) heappush(que,(0,0,0)) INF=float('inf') mi_y=[INF]*n mi_y[0]=0 ans=INF while que: cm,cy,ci=heappop(que) if ci==n-1: ans=min(cm,ans) for ni,ny,nm in edge[ci]: sm=cm+nm sy=cy+ny if sy>c: continue if mi_y[ni]<sy: continue heappush(que,(sm,sy,ni)) print(ans if ans!=INF else -1)