結果
問題 | No.2387 Yokan Factory |
ユーザー |
![]() |
提出日時 | 2023-07-23 13:41:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,565 ms / 5,000 ms |
コード長 | 864 bytes |
コンパイル時間 | 269 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 200,380 KB |
最終ジャッジ日時 | 2024-09-24 14:30:29 |
合計ジャッジ時間 | 23,905 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
N,M,X = map(int,input().split())UVAB = [list(map(int,input().split())) for _ in range(M)]E = [[] for _ in range(N)]maxa = 0for u,v,a,b in UVAB:u -= 1v -= 1E[u].append((v,a,b))E[v].append((u,a,b))maxa = max(maxa,b)INF = 10 ** 18from heapq import *#普通のダイクストラdef dijkstra(x):D = [INF] * ND[0] = 0q = [(0,0)]while len(q) > 0:d, u = heappop(q)#下のifでTLE解消することがあるif d > D[u]: continuefor vab in E[u]:v,a,b = vabif b < x:continueif D[v] > D[u] + a:D[v] = D[u] + aheappush(q, (D[v], v))return D[N-1]lb = -1ub = maxa + 1while ub - lb > 1:mid = (lb + ub)//2if dijkstra(mid) <= X:lb = midelse:ub = midprint(lb)