結果

問題 No.1607 Kth Maximum Card
ユーザー lam6er
提出日時 2025-04-09 20:56:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,615 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 376,408 KB
最終ジャッジ日時 2025-04-09 20:57:29
合計ジャッジ時間 10,923 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 6 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    edges = []
    for _ in range(M):
        u = int(input[ptr]); ptr +=1
        v = int(input[ptr]); ptr +=1
        c = int(input[ptr]); ptr +=1
        edges.append((u-1, v-1, c))

    # Compute shortest path length (minimum edges)
    adj_short = [[] for _ in range(N)]
    for u, v, _ in edges:
        adj_short[u].append(v)
        adj_short[v].append(u)
    
    dist = [-1]*N
    q = deque([0])
    dist[0] = 0
    while q:
        u = q.popleft()
        for v in adj_short[u]:
            if dist[v] == -1:
                dist[v] = dist[u] +1
                q.append(v)
    L = dist[N-1]

    if L < K:
        print(0)
        return
    
    # Need to compute minimal x
    # Collect all possible c_i for binary search
    cs = sorted(list(set(c for _, _, c in edges)))
    cs.sort()
    left = 0
    right = len(cs)-1
    answer = cs[-1]

    # Pre-sort edges by c
    edges_sorted = sorted(edges, key=lambda x: x[2])

    def is_possible(x):
        # Build adjacency list with edges >=x
        adj = [[] for _ in range(N)]
        for u, v, c in edges:
            if c >= x:
                adj[u].append(v)
                adj[v].append(u)
        # BFS to find component of N-1 and check if it has edges
        visited = [False]*N
        q = deque([N-1])
        visited[N-1] = True
        node_count = 1
        edge_count = 0
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    node_count +=1
                    q.append(v)
                edge_count +=1
        edge_count = edge_count //2
        if node_count >=2 and edge_count >=1:
            return True
        # If the component of N-1 has edges (S), then return True
        # Else, check if in original graph we can collect K edges >=x
        # Now, use BFS to track the maximum number of edges >=x along any path to N-1
        adj_orig = [[] for _ in range(N)]
        for u, v, c in edges:
            adj_orig[u].append((v, 1 if c >=x else 0))
            adj_orig[v].append((u, 1 if c >=x else 0))
        
        max_count = [-1]*N
        max_count[0] = 0
        q = deque()
        q.append((0, 0))
        # Using a priority approach
        # We use a deque to process nodes with higher counts first (0-1 BFS)
        # This is to track the maximum count for each node
        while q:
            u, cnt = q.popleft()
            if u == N-1 and cnt >= K:
                return True
            for (v, w) in adj_orig[u]:
                new_cnt = cnt + w
                if new_cnt > max_count[v]:
                    max_count[v] = new_cnt
                    if w == 1:
                        q.append((v, new_cnt))
                    else:
                        q.appendleft((v, new_cnt))
        if max_count[N-1] >= K:
            return True
        # Additionally, check if there's any cycle with edges >=x
        # Which is complex, so for time, skip. It's possible previous check missed some cases.
        # So, incomplete solution.
        return False

    low = 0
    high = len(cs) -1
    answer = cs[-1]
    # Binary search
    while low <= high:
        mid = (low + high) //2
        x = cs[mid]
        if is_possible(x):
            answer = x
            high = mid -1
        else:
            low = mid +1

    print(answer)

if __name__ == '__main__':
    main()
0