Day 072-Q4 — パラメトリック最短路（Parametric Shortest Path・凸最小化）

問題

$N$ 頂点 $M$ 辺の有向グラフがある。辺 $e_i$ は頂点 $u_i$ から $v_i$ へ向かい、コスト $c_i + \lambda \cdot d_i$ を持つ（$\lambda$ はパラメータ）。

頂点 $s$ から $t$ への最短路長 $f(\lambda) = \min_{\text{path}} \sum_{e \in P} (c_e + \lambda d_e)$ を考える。

1. $f(\lambda)$ が $\lambda$ の区分線形凸関数であることを確認
2. $f(\lambda) = 0$ となる $\lambda^*$ を二分探索で求めよ
3. $\lambda^*$ における最短路の経路を出力せよ

入出力例

4 5 1 4
1 2 3 -1
1 3 1 2
2 4 2 1
3 4 5 -1
2 3 1 0

Lambda*: 1.000
Path: 1 -> 2 -> 4
Total cost at lambda*: 5.0

概念図: 区分線形凸関数 f(λ) と二分探索

ヒント（段階的開示）

import heapq

def dijkstra(N, adj, s, t, lam):
    dist = [float('inf')] * (N+1)
    dist[s] = 0.0
    pq = [(0.0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, c, di in adj[u]:
            nd = d + c + lam * di
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist[t]

# 二分探索
lo, hi = -1e6, 1e6
for _ in range(200):
    mid = (lo + hi) / 2
    if dijkstra(N, adj, s, t, mid) > 0:
        lo = mid
    else:
        hi = mid

模範解答 (Python)

コピーimport sys
import heapq
input = sys.stdin.readline

def solve():
    N, M, s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u, v, c, d = map(int, input().split())
        adj[u].append((v, c, d))

    INF = float('inf')

    def dijkstra_with_path(lam):
        dist = [INF] * (N+1)
        prev = [-1] * (N+1)
        dist[s] = 0.0
        pq = [(0.0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u] + 1e-12: continue
            for v, c, di in adj[u]:
                nd = d + c + lam * di
                if nd < dist[v] - 1e-12:
                    dist[v] = nd
                    prev[v] = u
                    heapq.heappush(pq, (nd, v))
        return dist[t], prev

    def f(lam):
        val, _ = dijkstra_with_path(lam)
        return val

    f_lo = f(-1e6)
    f_hi = f(1e6)
    if f_lo * f_hi > 0:
        print("No solution in range")
        return

    lo, hi = -1e6, 1e6
    for _ in range(200):
        mid = (lo + hi) / 2
        if f(mid) > 0:
            lo = mid
        else:
            hi = mid

    lam_star = (lo + hi) / 2
    val, prev = dijkstra_with_path(lam_star)

    print(f"Lambda*: {lam_star:.3f}")

    path = []
    cur = t
    while cur != -1:
        path.append(cur)
        cur = prev[cur]
    path.reverse()
    print("Path:", " -> ".join(map(str, path)))
    print(f"Total cost at lambda*: {val:.1f}")

solve()

Step-by-Step 解説

Step 1: f(λ) の凸性

各固定パス $P$ のコストは $\lambda$ の1次式 $C_P + \lambda D_P$（ここで $C_P = \sum c_e$、$D_P = \sum d_e$）。

$f(\lambda) = \min_P (C_P + \lambda D_P)$ は線形関数の最小値なので凸関数（区分線形）。

Step 2: 二分探索の適用

$f$ が連続凸関数であり $f(\lambda) = 0$ の解が存在するなら、$f(\lambda_0) > 0$、$f(\lambda_1) < 0$ となる $\lambda_0 < \lambda_1$ を見つけて二分探索。

200 回反復で精度 $|f(\lambda^*)| < 10^{-9}$ が得られる。

Step 3: Dijkstra の反復

各反復で Dijkstra を実行（$O(M \log N)$）、合計 $O(M \log N \times 200) \approx 10^8$。

Step 4: 経路復元

最終的な $\lambda^*$ での Dijkstra の prev テーブルから $t$ を逆追跡。

よくあるミス

次のステップ

• 発展問題: パラメトリック最小カット（PARAMETRIC MAX-FLOW）
• 凸関数の傾き（劣微分）の追跡
• Aliens Trick との関係（ラグランジュ緩和・WQS 二分探索）

自己評価