結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
|
提出日時 | 2024-09-03 02:26:34 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,477 bytes |
コンパイル時間 | 536 ms |
コンパイル使用メモリ | 82,392 KB |
実行使用メモリ | 375,400 KB |
最終ジャッジ日時 | 2024-09-03 02:26:51 |
合計ジャッジ時間 | 7,979 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 3 -- * 25 |
ソースコード
## https://yukicoder.me/problems/no/1607 from collections import deque MAX_INT = 10 ** 18 def solve(N, edges, K, value): next_nodes = [[] for _ in range(N)] for u, v, c in edges: if c > value: next_nodes[u].append((v, 1)) next_nodes[v].append((u, 1)) else: next_nodes[u].append((v, 0)) next_nodes[v].append((u, 0)) # 01BFSで問題を解く dists = [MAX_INT ] * N dists[0] = 0 queue = deque() queue.append(0) while len(queue) > 0: v = queue.popleft() for w, cost in next_nodes[v]: if cost == 1: if dists[w] > dists[v] + 1: dists[w] = dists[v] + 1 queue.append(w) elif cost == 0: if dists[w] > dists[v]: dists[w] = dists[v] queue.appendleft(w) return dists[N - 1] < K def main(): N, M, K = map(int, input().split()) edges = [] max_c = 0 for _ in range(M): u, v, c = map(int, input().split()) edges.append((u - 1, v - 1, c)) max_c = max(c, max_c) low = 0 high = max_c while high - low > 1: mid = (high + low) // 2 if solve(N, edges, K, mid): high = mid else: low = mid if solve(N, edges, K, low): print(low) else: print(high) if __name__ == "__main__": main()