Day 162-Q5 — 2026-09-27 — 牛ゲー（差分制約系を最短路で解く。始点から届かない負閉路も「解なし」と判定する）

📋 コピーimport sys

INF = float("inf")


def bellman_ford(n, edges, dist):
    """dist を初期値として緩和を最大 n 周。n 周目にまだ更新されたら負閉路あり（False を返す）"""
    for it in range(n):
        updated = False
        for u, v, w in edges:
            du = dist[u]
            if du != INF and du + w < dist[v]:
                dist[v] = du + w
                updated = True
        if not updated:
            return True
    return False


def main():
    data = sys.stdin.buffer.read().split()
    n, ml, md = int(data[0]), int(data[1]), int(data[2])
    edges = []
    p = 3
    for _ in range(ml):                     # x_b - x_a <= d  →  辺 a→b 重み d
        a, b, d = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]); p += 3
        edges.append((a, b, d))
    for _ in range(md):                     # x_b - x_a >= d  ⇔  x_a - x_b <= -d  →  辺 b→a 重み -d
        a, b, d = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]); p += 3
        edges.append((b, a, -d))
    for i in range(n - 1):                  # x_i <= x_{i+1}  ⇔  x_i - x_{i+1} <= 0  →  辺 i+1→i 重み 0
        edges.append((i + 1, i, 0))
    # 1) 解があるか: 全頂点を距離 0 で始める（仮想の始点から重み 0 の辺を全頂点へ張ったのと同じ）
    if not bellman_ford(n, edges, [0] * n):
        print(-1)
        return
    # 2) 最大の x_N - x_1 = 頂点 1 から頂点 N への最短距離
    dist = [INF] * n
    dist[0] = 0
    bellman_ford(n, edges, dist)            # 1) で負閉路が無いと分かっているので必ず収束する
    print(-2 if dist[n - 1] == INF else dist[n - 1])


main()