結果
問題 | No.2739 Time is money |
ユーザー |
|
提出日時 | 2024-04-20 10:55:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,270 ms / 2,000 ms |
コード長 | 915 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 151,476 KB |
最終ジャッジ日時 | 2024-10-12 06:32:11 |
合計ジャッジ時間 | 16,747 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import heapq N,M,X=map(int,input().split()) G=[{} for i in range(N)] for j in range(M): u,v,c,t=map(int,input().split()) u-=1 v-=1 G[u][v]=(c,t) G[v][u]=(c,t) def dijkstra(s,g): cost=[float("inf")]*N prev=[None]*N cost[s]=0 Q=[(0,s)] heapq.heapify(Q) while Q: d,v=heapq.heappop(Q) if d>cost[v]: continue for u in G[v]: c,t=G[u][v] #(かかる時間)=c/X+t money=c+X*t if cost[v]+money<cost[u]: cost[u]=cost[v]+money heapq.heappush(Q,(cost[u],u)) prev[u]=v if prev[g] is None: return -1 else: c=0 t=0 v=g u=prev[v] while u is not None: c+=G[u][v][0] t+=G[u][v][1] v=u u=prev[v] return (c+X-1)//X+t print(dijkstra(0,N-1))