結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
|
提出日時 | 2021-08-14 13:04:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,896 ms / 3,500 ms |
コード長 | 788 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 144,132 KB |
最終ジャッジ日時 | 2024-10-05 05:20:57 |
合計ジャッジ時間 | 21,987 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
from collections import deque n, m, k = map(int, input().split()) G = [[] for i in range(n)] for _ in range(m): u, v, c = map(int, input().split()) u -= 1; v -= 1 G[u].append((v, c)) G[v].append((u, c)) def ok(x): Q = deque([0]) d = [-1] * n d[0] = 0 while Q: u = Q.popleft() for v, c in G[u]: if c > x: if d[v] == -1 or (d[u] != -1 and d[v] > d[u] + 1): d[v] = d[u] + 1 Q.append(v) else: if d[v] == -1 or (d[u] != -1 and d[v] > d[u]): d[v] = d[u] Q.appendleft(v) return d[-1] < k l, r = -1, 10 ** 6 while r - l > 1: M = (l + r) // 2 if ok(M): r = M else: l = M print(r)