結果
問題 | No.1607 Kth Maximum Card |
ユーザー | ああいい |
提出日時 | 2022-03-07 11:36:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,296 ms / 3,500 ms |
コード長 | 1,418 bytes |
コンパイル時間 | 520 ms |
コンパイル使用メモリ | 87,072 KB |
実行使用メモリ | 157,700 KB |
最終ジャッジ日時 | 2023-09-29 10:37:29 |
合計ジャッジ時間 | 27,410 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 93 ms
71,708 KB |
testcase_01 | AC | 94 ms
71,648 KB |
testcase_02 | AC | 94 ms
71,544 KB |
testcase_03 | AC | 94 ms
71,848 KB |
testcase_04 | AC | 93 ms
71,540 KB |
testcase_05 | AC | 93 ms
71,616 KB |
testcase_06 | AC | 92 ms
71,452 KB |
testcase_07 | AC | 92 ms
71,628 KB |
testcase_08 | AC | 1,795 ms
143,016 KB |
testcase_09 | AC | 1,029 ms
121,612 KB |
testcase_10 | AC | 2,296 ms
157,700 KB |
testcase_11 | AC | 285 ms
92,956 KB |
testcase_12 | AC | 1,511 ms
129,732 KB |
testcase_13 | AC | 319 ms
85,568 KB |
testcase_14 | AC | 366 ms
89,988 KB |
testcase_15 | AC | 1,201 ms
121,372 KB |
testcase_16 | AC | 275 ms
88,000 KB |
testcase_17 | AC | 212 ms
80,664 KB |
testcase_18 | AC | 836 ms
103,904 KB |
testcase_19 | AC | 498 ms
94,384 KB |
testcase_20 | AC | 666 ms
96,840 KB |
testcase_21 | AC | 783 ms
99,476 KB |
testcase_22 | AC | 1,209 ms
138,036 KB |
testcase_23 | AC | 1,343 ms
138,076 KB |
testcase_24 | AC | 706 ms
93,616 KB |
testcase_25 | AC | 467 ms
90,708 KB |
testcase_26 | AC | 557 ms
89,876 KB |
testcase_27 | AC | 826 ms
93,956 KB |
testcase_28 | AC | 660 ms
91,232 KB |
testcase_29 | AC | 1,279 ms
113,708 KB |
testcase_30 | AC | 2,246 ms
137,056 KB |
testcase_31 | AC | 1,279 ms
111,520 KB |
testcase_32 | AC | 297 ms
98,716 KB |
testcase_33 | AC | 290 ms
98,668 KB |
testcase_34 | AC | 333 ms
98,732 KB |
testcase_35 | AC | 339 ms
98,656 KB |
ソースコード
import sys rr = sys.stdin N,M,K = map(int,rr.readline().split()) G = [[] for _ in range(N+1)] for _ in range(M): a,b,c = map(int,rr.readline().split()) G[a].append((b,c)) G[b].append((a,c)) import heapq inf = 10 ** 6 base = 23 mask = (1 << base) - 1 """ def calc(x): dist = [K] * (N+1) dist[1] = 0 q = [1] while q: u = heapq.heappop(q) d,now = u >> base,u & mask if now == N:break if dist[now] < d: continue for v,c in G[now]: if c > x: c = 1 else: c = 0 if dist[v] > d + c: dist[v] = d + c heapq.heappush(q,(d+c) << base | v) return dist[N] < K """ from collections import deque def calc(x): dist = [inf] * (N+1) dist[1] = 0 q = deque() q.append((0,1)) while q: d,now = q.popleft() if now == N:break if dist[now] < d:continue for v,c in G[now]: if c > x: if dist[v] > d + 1: dist[v] = d + 1 q.append((d+1,v)) else: if dist[v] > d: dist[v] = d q.appendleft((d,v)) return dist[N] < K start = -1 end = 2 * 10 ** 5 while end - start > 1: mid = (end + start) // 2 if calc(mid): end = mid else: start = mid print(end)