Day 062-Q5 | Johnson再ポテンシャル法（辺重み変動・動的最短路）

問題

$N$ 頂点 $M$ 辺の有向グラフ（辺重みに負の値を含む可能性あり）に対し、$Q$ 個のオンラインクエリを処理せよ：

型 1: 1 e d — 辺番号 $e$ の重みに $d$ を加算
型 2: 2 s t — 頂点 $s$ から $t$ への最短路距離を出力（到達不可 = $-1$）

グラフに負閉路は常に存在しない（変更後も）。

制約

パラメータ	範囲
$N$	$2 \le N \le 500$
$M$	$1 \le M \le 2000$
$\|w_i\|$	$\le 10^9$
$Q$	$1 \le Q \le 1000$

入出力例

入力例 1

出力例 1

2
0
-5

初期: $1 \to 3$の最短路は $1 \to 2 \to 3 = -3+5=2$。辺1を $-5$ に変更後: $-5+5=0$。辺2を $-15$ に変更後: $-5+(-15)=-20$ ... など確認。

概念図: Johnson ポテンシャルの仕組み

ヒント（段階的開示）

ヒント1: 方向性

Johnson 法はポテンシャル $h[v]$（仮想始点からの最短路）を使って辺重みを $w'(u,v) = w(u,v) + h[u] - h[v] \ge 0$ に変換し、Dijkstra を適用可能にする技法。辺重み変更後はポテンシャルを Bellman-Ford で再計算する。

ヒント2: アプローチ

仮想頂点 $0$ を追加し全頂点へ重み $0$ の辺を追加
Bellman-Ford で $h[v]$ を計算（$O(NM)$）
型 1 クエリ: 辺重み更新後に Bellman-Ford 再実行
型 2 クエリ: 変換後重みで Dijkstra（$O((N+M)\log N)$）、実距離 = 結果 $+ h[t] - h[s]$

ヒント3: コード骨格

def bellman_ford(N, edges, src):
    dist = [INF]*(N+1); dist[src] = 0
    for _ in range(N):
        for u, v, w in edges:
            if dist[u] < INF and dist[u]+w < dist[v]:
                dist[v] = dist[u]+w
    return dist

# 初期化: 仮想辺追加
virtual = edges + [(0, v, 0) for v in range(1, N+1)]
h = bellman_ford(N, virtual, 0)

# 型1クエリ後: h を再計算
# 型2クエリ: Dijkstra(h) → 実距離 = d[t] + h[t] - h[s]

模範解答 (Python)

import sys
import heapq
input = sys.stdin.readline

INF = float('inf')

def bellman_ford(N, edges, src):
    dist = [INF] * (N + 1)
    dist[src] = 0
    for _ in range(N):
        updated = False
        for u, v, w in edges:
            if dist[u] < INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated: break
    return dist

def dijkstra(N, adj, h, src, edges):
    dist = [INF] * (N + 1)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]: continue
        for u, eid in adj[v]:
            w = edges[eid][2]
            reduced_w = w + h[v] - h[u]
            nd = d + reduced_w
            if nd < dist[u]:
                dist[u] = nd
                heapq.heappush(pq, (nd, u))
    result = []
    for t in range(N + 1):
        if dist[t] == INF: result.append(-1)
        else: result.append(dist[t] + h[t] - h[src])
    return result

def main():
    N, M = map(int, input().split())
    edges = []
    adj = [[] for _ in range(N + 1)]
    for eid in range(M):
        u, v, w = map(int, input().split())
        edges.append([u, v, w])
        adj[u].append((v, eid))

    def compute_h():
        virtual = [[0, v, 0] for v in range(1, N+1)] + edges
        return bellman_ford(N, virtual, 0)

    h = compute_h()

    Q = int(input())
    out = []
    for _ in range(Q):
        tokens = input().split()
        if tokens[0] == '1':
            eid = int(tokens[1]) - 1
            d = int(tokens[2])
            edges[eid][2] += d
            h = compute_h()
        else:
            s, t = int(tokens[1]), int(tokens[2])
            dists = dijkstra(N, adj, h, s, edges)
            out.append(str(dists[t]))
    print('\n'.join(out))

main()

Step-by-Step 解説

Step 1: Johnson ポテンシャルの計算

仮想頂点 $0$ から全頂点に重み $0$ の辺を追加し、Bellman-Ford で $h[v]$（$0$ からの最短路）を計算。これにより変換後の辺重み $w'(u,v) = w(u,v) + h[u] - h[v] \ge 0$ が保証される（三角不等式より）。計算量 $O(NM)$。

Step 2: 辺重み変更後のポテンシャル再計算

型 1 クエリで辺重みを変更した後、Bellman-Ford を再実行してポテンシャルを更新する。$Q$ クエリで最悪 $O(QNM)$。本問の制約（$Q \le 1000, NM \le 10^6$）では許容範囲。

Step 3: Dijkstra による最短路クエリ

変換後の辺重みで Dijkstra を実行。計算量 $O((N+M)\log N)$。実際の距離は Dijkstra 距離 $+ h[t] - h[s]$（変換を元に戻す）。

よくあるミス

ミス	原因	正しい書き方
変換後重みの符号ミス	$h[v] - h[u]$ と逆にする	$w'(u,v) = w + h[u] - h[v]$
実距離の復元ミス	$h[s] - h[t]$ と逆	実距離 $= $ Dijkstra距離 $+ h[t] - h[s]$
辺重み変更後に $h$ を更新しない	古い $h$ で変換すると負辺が生じる	型1クエリ毎に Bellman-Ford 再実行

次のステップ

発展問題: 辺追加のみの場合は Johnson 差分更新で $O(N \log N)$ per クエリ（Incremental SSSP）
関連: 動的最短路・Decremental SSSP（辺削除）・感度分析（sensitivity analysis of shortest paths）

自己評価

完全理解おおむね理解要復習