結果
問題 |
No.2387 Yokan Factory
|
ユーザー |
![]() |
提出日時 | 2023-07-21 21:36:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,526 ms / 5,000 ms |
コード長 | 1,188 bytes |
コンパイル時間 | 242 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 186,880 KB |
最終ジャッジ日時 | 2024-09-21 22:56:54 |
合計ジャッジ時間 | 22,562 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
############################################################# import sys sys.setrecursionlimit(10**7) from heapq import heappop,heappush from collections import deque,defaultdict,Counter from bisect import bisect_left, bisect_right from itertools import product,combinations,permutations ipt = sys.stdin.readline def iin(): return int(ipt()) def lmin(): return list(map(int,ipt().split())) inf = 1<<60 MOD = 998244353 ############################################################# N,M,X = lmin() G = [[] for _ in range(N)] for _ in range(M): u,v,a,b = lmin() u,v = u-1,v-1 G[u].append((v,a,b)) G[v].append((u,a,b)) def check(cen): cost = [inf]*N cost[0] = 0 hq = [] heappush(hq, (0,0)) while hq: t,cur = heappop(hq) if t > cost[cur]: continue for nxt,a,b in G[cur]: if b < cen: continue nt = t+a if nt < cost[nxt]: cost[nxt] = nt heappush(hq, (nt, nxt)) return cost[-1] <= X ok = -1 ng = 1<<30 while ng - ok > 1: cen = (ok+ng)//2 if check(cen): ok = cen else: ng = cen print(ok)