結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
![]() |
提出日時 | 2021-04-09 01:04:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,397 ms / 3,500 ms |
コード長 | 1,536 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 165,828 KB |
最終ジャッジ日時 | 2024-07-06 07:48:31 |
合計ジャッジ時間 | 17,496 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
""" 二分探索の想定解 K番目の数字がX以下かを判定する Xが大きければ当然OKになりやすく 小さければNOになりやすい Xより大きい数字をK個未満通って到達できるかを判定すればよい """ from collections import deque from sys import stdin def Bfs_01(X): q = deque([0]) dlis = [float("inf")] * N dlis[0] = 0 while q: nowv = q.popleft() for nexv,cost in lis[nowv]: if cost > X: if dlis[nexv] > dlis[nowv] + 1: dlis[nexv] = dlis[nowv] + 1 q.append(nexv) else: if dlis[nexv] > dlis[nowv]: dlis[nexv] = dlis[nowv] q.appendleft(nexv) assert max(dlis) != float("inf") return dlis N,M,K = map(int,stdin.readline().split()) #制約チェック assert 2 <= N <= 2*(10**5) assert N-1 <= M <= min(2*(10**5) , N*(N-1)//2) assert 1 <= K <= 2*(10**5) lis = [ [] for i in range(N) ] #隣接リスト uvset = set() #辺が被っていないかのチェック用 for i in range(M): u,v,c = map(int,stdin.readline().split()) #制約チェック assert 1 <= u < v <= N assert (u,v) not in uvset uvset.add( (u,v) ) assert 1 <= c <= 2*(10**5) u -= 1 v -= 1 lis[u].append((v,c)) lis[v].append((u,c)) l = -1 r = 2*(10**5) while r-l != 1: X = (l+r)//2 dlis = Bfs_01(X) if dlis[N-1] < K: r = X else: l = X print (r)