結果

問題 No.1393 Median of Walk
ユーザー qwewe
提出日時 2025-05-14 12:51:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,764 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 104,216 KB
最終ジャッジ日時 2025-05-14 12:52:44
合計ジャッジ時間 4,470 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1

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

    # Collect all unique edge weights and sort them
    sorted_weights = sorted({w for _, _, w in edges})
    sorted_weights.append(float('inf'))  # To handle unreachable cases

    # Initialize answer for each node (2 to N)
    answer = [-1] * (N + 1)  # 1-based indexing

    # Process each x in sorted order
    for x in sorted_weights:
        # Build the contribution graph
        contribution = {}
        adj = [[] for _ in range(N+1)]  # adjacency list for BFS later
        for u, v, w in edges:
            c = 1 if w <= x else -1
            contribution[(u, v)] = c
            adj[u].append(v)  # for BFS later

        # Bellman-Ford to compute maximum sum
        dist = [-float('inf')] * (N + 1)
        dist[1] = 0
        for _ in range(N - 1):
            updated = False
            for u, v, w in edges:
                c = contribution[(u, v)]
                if dist[u] != -float('inf') and dist[v] < dist[u] + c:
                    dist[v] = dist[u] + c
                    updated = True
            if not updated:
                break

        # Check for nodes that can be relaxed in the Nth iteration (positive cycles)
        in_cycle = set()
        for u, v, w in edges:
            c = contribution[(u, v)]
            if dist[u] != -float('inf') and dist[v] < dist[u] + c:
                in_cycle.add(v)

        # BFS to find all nodes reachable from any node in in_cycle
        visited = [False] * (N + 1)
        q = deque()
        for node in in_cycle:
            if not visited[node]:
                q.append(node)
                visited[node] = True
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)

        # Update answers
        for i in range(2, N + 1):
            if answer[i] == -1:
                if dist[i] >= 0:
                    answer[i] = x
                elif visited[i] and dist[i] != -float('inf'):
                    answer[i] = x

        # Check if all nodes are processed
        all_processed = True
        for i in range(2, N + 1):
            if answer[i] == -1:
                all_processed = False
                break
        if all_processed:
            break

    # Output the answers for nodes 2 to N
    for i in range(2, N + 1):
        print(answer[i])

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