#1172115 (PyPy3) No.3784 01 Walk

• 問題: No.3784 01 Walk
• ユーザー: askr58
• 提出日時: 2026-07-20 06:11:34
• 言語: PyPy3 (8.0.0 + ACL)
• 結果: AC
• 実行時間: 1,213 ms / 2,000 ms
• コード長: 7,899 bytes
• コンパイル時間: 431 ms
• コンパイル使用メモリ: 64,524 KB
• 実行使用メモリ: 185,748 KB
• 最終ジャッジ日時: 2026-10-30 20:53:12
• 合計ジャッジ時間: 51,108 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 40

ソースコード

#generated by ChatGPT
import sys
from collections import deque


def main():
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())

    # 状態 (v, parity) を 2*v + parity で表す。
    # 元頂点 v は 0-indexed。
    V = 2 * N

    graph = [[] for _ in range(V)]
    reverse_graph = [[] for _ in range(V)]

    for _ in range(M):
        u, v, c = map(int, input().split())
        u -= 1
        v -= 1

        w = 2 * c - 1

        # |A| が偶数の場合
        from_vertex = 2 * u
        to_vertex = 2 * v + 1

        graph[from_vertex].append((to_vertex, w))
        reverse_graph[to_vertex].append(from_vertex)

        # |A| が奇数の場合
        from_vertex = 2 * u + 1
        to_vertex = 2 * v

        graph[from_vertex].append((to_vertex, -w))
        reverse_graph[to_vertex].append(from_vertex)

    # ------------------------------------------------------------
    # Kosaraju 法: 1 回目の DFS
    # ------------------------------------------------------------

    used = bytearray(V)
    order = []

    for start in range(V):
        if used[start]:
            continue

        used[start] = 1

        # (頂点, 次に見る辺の添字)
        stack = [(start, 0)]

        while stack:
            vertex, edge_index = stack[-1]

            if edge_index < len(graph[vertex]):
                to = graph[vertex][edge_index][0]
                stack[-1] = (vertex, edge_index + 1)

                if not used[to]:
                    used[to] = 1
                    stack.append((to, 0))
            else:
                order.append(vertex)
                stack.pop()

    # ------------------------------------------------------------
    # Kosaraju 法: 2 回目の DFS
    # ------------------------------------------------------------

    component = [-1] * V
    component_count = 0

    for start in reversed(order):
        if component[start] != -1:
            continue

        component[start] = component_count
        stack = [start]

        while stack:
            vertex = stack.pop()

            for to in reverse_graph[vertex]:
                if component[to] == -1:
                    component[to] = component_count
                    stack.append(to)

        component_count += 1

    # ------------------------------------------------------------
    # SCC 内のポテンシャルを求める
    #
    # 内部辺 v -> to, 重み w に対して
    #
    #     potential[to] = potential[v] + w
    #
    # が矛盾するなら、その SCC には重み非零の閉路がある。
    # ------------------------------------------------------------

    INF = 10**30

    potential = [INF] * V
    bad_component = bytearray(component_count)

    for start in range(V):
        if potential[start] != INF:
            continue

        component_id = component[start]

        potential[start] = 0
        stack = [start]

        while stack:
            vertex = stack.pop()
            current_potential = potential[vertex]

            for to, weight in graph[vertex]:
                if component[to] != component_id:
                    continue

                next_potential = current_potential + weight

                if potential[to] == INF:
                    potential[to] = next_potential
                    stack.append(to)
                elif potential[to] != next_potential:
                    bad_component[component_id] = 1

    # ------------------------------------------------------------
    # SCC を縮約した DAG を構築
    #
    # SCC 内では
    #
    #     base = X - potential[vertex]
    #
    # が一定。
    #
    # SCC 間の辺 v -> to, 重み w では base の変化量は
    #
    #     potential[v] + w - potential[to]
    #
    # となる。
    #
    # 同じ SCC 間に複数の辺があっても、すべて個別に保持する。
    # ------------------------------------------------------------

    dag = [[] for _ in range(component_count)]
    indegree = [0] * component_count

    for vertex in range(V):
        from_component = component[vertex]
        from_potential = potential[vertex]

        for to, weight in graph[vertex]:
            to_component = component[to]

            if from_component == to_component:
                continue

            delta = (
                from_potential
                + weight
                - potential[to]
            )

            dag[from_component].append((to_component, delta))
            indegree[to_component] += 1

    # ------------------------------------------------------------
    # 縮約 DAG のトポロジカルソート
    # ------------------------------------------------------------

    queue = deque()

    for component_id in range(component_count):
        if indegree[component_id] == 0:
            queue.append(component_id)

    topological_order = []

    while queue:
        component_id = queue.popleft()
        topological_order.append(component_id)

        for to, _ in dag[component_id]:
            indegree[to] -= 1

            if indegree[to] == 0:
                queue.append(to)

    # ------------------------------------------------------------
    # DAG 上の DP
    #
    # minimum_base[c]:
    #     SCC c に到達するときの base の最小値
    #
    # maximum_base[c]:
    #     SCC c に到達するときの base の最大値
    #
    # unbounded[c]:
    #     SCC c で |X| を非有界にできるか
    # ------------------------------------------------------------

    minimum_base = [INF] * component_count
    maximum_base = [-INF] * component_count
    unbounded = bytearray(component_count)

    source = 0  # 元頂点1、偶数状態
    source_component = component[source]

    source_base = -potential[source]

    minimum_base[source_component] = source_base
    maximum_base[source_component] = source_base

    for component_id in topological_order:
        if minimum_base[component_id] == INF:
            # 始点から到達不能
            continue

        if bad_component[component_id]:
            unbounded[component_id] = 1

        current_minimum = minimum_base[component_id]
        current_maximum = maximum_base[component_id]
        current_unbounded = unbounded[component_id]

        for to, delta in dag[component_id]:
            candidate_minimum = current_minimum + delta
            candidate_maximum = current_maximum + delta

            if candidate_minimum < minimum_base[to]:
                minimum_base[to] = candidate_minimum

            if candidate_maximum > maximum_base[to]:
                maximum_base[to] = candidate_maximum

            if current_unbounded:
                unbounded[to] = 1

    # ------------------------------------------------------------
    # 各元頂点の答えを求める
    # ------------------------------------------------------------

    answers = []

    for vertex in range(N):
        answer = 0
        infinite = False

        for parity in range(2):
            state = 2 * vertex + parity
            component_id = component[state]

            if minimum_base[component_id] == INF:
                # この偶奇状態には到達不能
                continue

            if unbounded[component_id]:
                infinite = True
                break

            minimum_x = (
                minimum_base[component_id]
                + potential[state]
            )

            maximum_x = (
                maximum_base[component_id]
                + potential[state]
            )

            answer = max(
                answer,
                abs(minimum_x),
                abs(maximum_x),
            )

        if infinite:
            answers.append("-1")
        else:
            answers.append(str(answer))

    print("\n".join(answers))


if __name__ == "__main__":
    main()