結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2025-04-24 12:27:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,842 ms / 3,500 ms |
コード長 | 1,284 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 176,400 KB |
最終ジャッジ日時 | 2025-04-24 12:29:10 |
合計ジャッジ時間 | 19,302 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import sys from collections import deque def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 K = int(input[ptr]) ptr += 1 adj = [[] for _ in range(N + 1)] max_c = 0 for _ in range(M): u = int(input[ptr]) ptr += 1 v = int(input[ptr]) ptr += 1 c = int(input[ptr]) ptr += 1 adj[u].append((v, c)) adj[v].append((u, c)) if c > max_c: max_c = c low = 0 high = max_c while low < high: mid = (low + high) // 2 dist = [float('inf')] * (N + 1) dist[1] = 0 q = deque([1]) found = False while q: u = q.popleft() if u == N: found = True break for (v, c) in adj[u]: w = 1 if c > mid else 0 if dist[v] > dist[u] + w: dist[v] = dist[u] + w if w == 0: q.appendleft(v) else: q.append(v) if found and dist[N] <= K - 1: high = mid else: low = mid + 1 print(low) if __name__ == "__main__": main()