結果

問題 No.1393 Median of Walk
ユーザー qwewe
提出日時 2025-05-14 12:53:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,523 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 89,848 KB
最終ジャッジ日時 2025-05-14 12:55:04
合計ジャッジ時間 7,107 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 2 -- * 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])-1; idx +=1
        v = int(input[idx])-1; idx +=1
        w = int(input[idx]); idx +=1
        edges.append( (u, v, w) )

    # Collect all unique edge weights and sort them
    ws = sorted( list( set( e[2] for e in edges )) )
    if not ws:
        for i in range(N-1):
            print(-1)
        return

    adj = [[] for _ in range(N)]
    for u, v, w in edges:
        adj[u].append( (v, w) )

    # Precompute for each node the possible answers
    ans = [ -1 ] * N

    # For each w in sorted order, check if it's a candidate
    for w in sorted(ws):
        # Build the modified graph with +1/-1
        mod_edges = []
        for u, v, weight in edges:
            if weight <= w:
                mod_edges.append( (u, v, 1) )
            else:
                mod_edges.append( (u, v, -1) )

        # Run Bellman-Ford to detect possible sum >=0 and positive cycles
        INF = -10**18
        dist = [ INF ] * N
        dist[0] = 0
        # Update N times to detect positive cycles
        for i in range(N):
            updated = False
            for u, v, w_mod in mod_edges:
                if dist[u] != INF and dist[v] < dist[u] + w_mod:
                    if i == N-1:
                        # Positive cycle detected, mark nodes reachable from this node
                        # Using BFS to find all nodes reachable from u
                        q = deque()
                        q.append(u)
                        reachable = set()
                        reachable.add(u)
                        while q:
                            node = q.popleft()
                            for nv, _ in adj[node]:
                                if nv not in reachable:
                                    reachable.add(nv)
                                    q.append(nv)
                        # Any node in reachable can be part of a path with sum >=0
                        for node in reachable:
                            if ans[node] == -1:
                                ans[node] = w
                        # Also, any node reachable from node v can be reached via the cycle
                        q = deque()
                        q.append(v)
                        reachable_from_v = set()
                        reachable_from_v.add(v)
                        while q:
                            node = q.popleft()
                            for nv, _ in adj[node]:
                                if nv not in reachable_from_v:
                                    reachable_from_v.add(nv)
                                    q.append(nv)
                        for node in reachable_from_v:
                            if ans[node] == -1:
                                ans[node] = w
                    else:
                        dist[v] = dist[u] + w_mod
                        updated = True
            if not updated:
                break

        # Check for nodes where dist[i] >=0 and ans[i] is not set
        for i in range(N):
            if ans[i] == -1 and dist[i] >=0:
                ans[i] = w

    # Handle node 0 (not needed)
    # Output for nodes 2..N (1-based)
    for i in range(1, N):
        if i ==0:
            continue
        print(ans[i] if ans[i] != -1 else -1)

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