結果
問題 |
No.2739 Time is money
|
ユーザー |
|
提出日時 | 2025-07-13 14:08:16 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,050 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,216 KB |
実行使用メモリ | 394,508 KB |
最終ジャッジ日時 | 2025-07-13 14:08:24 |
合計ジャッジ時間 | 5,227 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 1 TLE * 1 -- * 16 |
ソースコード
import heapq N,M,X = map(int,input().split()) G = {i:[] for i in range(1,N+1)} for _ in range(M): u,v,c,t = map(int,input().split()) G[u].append((v,c,t)) G[v].append((u,c,t)) INFTY = 10**12 ans = INFTY dist = {} visit = set() que = [(0,1,0)] dist[(1,0)] = 0 while que: t,v,c = heapq.heappop(que) if (v,c) in dist and dist[(v,c)]<t:continue if (v,c) in visit:continue visit.add((v,c)) for u,dc,dt in G[v]: if (u,c-dc) in visit:continue if c>=dc: nc = c-dc nt = t+dt if nt<dist.get((u,nc),INFTY): dist[(u,nc)] = nt if u==N: ans = min(ans,nt) heapq.heappush(que,(nt,u,nc)) else: k = (dc-c+X-1)//X nc = c+k*X-dc nt = t+k+dt if nt<dist.get((u,nc),INFTY): dist[(u,nc)] = nt if u==N: ans = min(ans,nt) heapq.heappush(que,(nt,u,nc)) if ans==INFTY: print(-1) else: print(ans)