結果

問題 No.1393 Median of Walk
ユーザー qwewe
提出日時 2025-04-24 12:27:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,794 bytes
コンパイル時間 144 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 78,148 KB
最終ジャッジ日時 2025-04-24 12:27:54
合計ジャッジ時間 4,892 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = []
    weights = set()
    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))
        weights.add(w)
    weights = sorted(weights)

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

    answers = [-1] * (N-1)

    for x in weights:
        new_edges = []
        for u, v, w in edges:
            if w <= x:
                new_edges.append((u, v, 1))
            else:
                new_edges.append((u, v, -1))

        dist = [-float('inf')] * (N+1)
        dist[1] = 0

        for _ in range(N-1):
            updated = False
            for u, v, w in new_edges:
                if dist[u] != -float('inf') and dist[v] < dist[u] + w:
                    dist[v] = dist[u] + w
                    updated = True
            if not updated:
                break

        in_cycle = set()
        for u, v, w in new_edges:
            if dist[u] != -float('inf') and dist[v] < dist[u] + w:
                in_cycle.add(v)

        visited = set()
        q = deque()
        for node in in_cycle:
            q.append(node)
            visited.add(node)
        while q:
            u = q.popleft()
            for v, _ in adj[u]:
                if v not in visited:
                    visited.add(v)
                    q.append(v)

        for i in range(2, N+1):
            if answers[i-2] == -1 and (dist[i] >= 0 or i in visited):
                answers[i-2] = x

    for ans in answers:
        print(ans)

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