結果
問題 | No.1607 Kth Maximum Card |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-04-09 01:04:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,337 ms / 3,500 ms |
コード長 | 1,536 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 86,648 KB |
実行使用メモリ | 163,716 KB |
最終ジャッジ日時 | 2023-09-20 12:27:56 |
合計ジャッジ時間 | 30,241 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 92 ms
71,416 KB |
testcase_01 | AC | 91 ms
71,644 KB |
testcase_02 | AC | 92 ms
71,420 KB |
testcase_03 | AC | 93 ms
71,628 KB |
testcase_04 | AC | 92 ms
71,280 KB |
testcase_05 | AC | 92 ms
71,724 KB |
testcase_06 | AC | 91 ms
71,660 KB |
testcase_07 | AC | 91 ms
71,552 KB |
testcase_08 | AC | 2,337 ms
161,268 KB |
testcase_09 | AC | 1,948 ms
146,928 KB |
testcase_10 | AC | 2,018 ms
163,716 KB |
testcase_11 | AC | 514 ms
96,068 KB |
testcase_12 | AC | 1,914 ms
144,880 KB |
testcase_13 | AC | 331 ms
90,040 KB |
testcase_14 | AC | 384 ms
94,412 KB |
testcase_15 | AC | 1,306 ms
143,416 KB |
testcase_16 | AC | 330 ms
91,096 KB |
testcase_17 | AC | 200 ms
81,380 KB |
testcase_18 | AC | 866 ms
117,416 KB |
testcase_19 | AC | 585 ms
103,088 KB |
testcase_20 | AC | 729 ms
109,236 KB |
testcase_21 | AC | 754 ms
111,736 KB |
testcase_22 | AC | 1,357 ms
159,152 KB |
testcase_23 | AC | 1,352 ms
160,668 KB |
testcase_24 | AC | 743 ms
102,308 KB |
testcase_25 | AC | 467 ms
93,484 KB |
testcase_26 | AC | 561 ms
96,824 KB |
testcase_27 | AC | 777 ms
103,068 KB |
testcase_28 | AC | 641 ms
97,868 KB |
testcase_29 | AC | 1,340 ms
127,080 KB |
testcase_30 | AC | 2,326 ms
160,184 KB |
testcase_31 | AC | 1,236 ms
121,172 KB |
testcase_32 | AC | 440 ms
119,248 KB |
testcase_33 | AC | 440 ms
119,216 KB |
testcase_34 | AC | 537 ms
119,216 KB |
testcase_35 | AC | 434 ms
119,264 KB |
ソースコード
""" 二分探索の想定解 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)