結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2025-03-20 19:01:22 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,034 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,756 KB |
実行使用メモリ | 385,012 KB |
最終ジャッジ日時 | 2025-03-20 19:02:41 |
合計ジャッジ時間 | 6,708 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 TLE * 4 -- * 5 |
ソースコード
import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N, M, K = map(int, sys.stdin.readline().split()) edges = [] max_c = 0 for _ in range(M): u, v, c = map(int, sys.stdin.readline().split()) edges.append((u, v, c)) if c > max_c: max_c = c # Step 1: Find the shortest path (minimum number of edges) adj_shortest = [[] for _ in range(N+1)] for u, v, c in edges: adj_shortest[u].append(v) adj_shortest[v].append(u) visited = [False] * (N+1) q = deque() q.append(1) visited[1] = True d = 0 found = False distance = [-1] * (N+1) distance[1] = 0 while q: u = q.popleft() if u == N: found = True break for v in adj_shortest[u]: if distance[v] == -1: distance[v] = distance[u] + 1 q.append(v) if not found: print(-1) return d = distance[N] if d <= K-1 and (K + d) >= K: print(0) return # Step 2: Binary search with 0-1 BFS left = 0 right = max_c answer = max_c while left <= right: mid = (left + right) // 2 adj = [[] for _ in range(N+1)] for u, v, c in edges: cost = 1 if c > mid else 0 adj[u].append((v, cost)) adj[v].append((u, cost)) # 0-1 BFS INF = float('inf') dist = [INF] * (N+1) dist[1] = 0 dq = deque() dq.append(1) while dq: u = dq.popleft() for v, w in adj[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w if w == 0: dq.appendleft(v) else: dq.append(v) if dist[N] <= K-1: answer = mid right = mid - 1 else: left = mid + 1 print(answer) if __name__ == '__main__': main()