結果

問題 No.1607 Kth Maximum Card
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0