Day 144-Q5 — Reach-based Pruning（到達値による最短路探索の枝刈り）

2026-09-05 赤色 Master / Phase 8+ ★★★★★★★★★ 到達値r(v)が始点距離・目的地への直線下界の両方を下回れば安全に探索を枝刈り(Gutman法)

問題

平面上の $N$ 頂点 $M$ 辺の道路網（辺重みは両端点のユークリッド距離以上）が与えられる。各頂点 $v$ には到達値（reach） $r(v)$ が与えられ、次を満たす:

$v$を通るある最短経路$a\to b$（$v\ne a,b$）が存在するなら $r(v) \ge \min(d(a,v),d(v,b))$。

頂点 $s$ から頂点 $t$ への最短距離を、到達値による枝刈りを用いたダイクストラ法で求めよ。

枝刈り規則

頂点$u$（$u\ne s,t$）を確定させる際、$\text{lb}(u,t)=\text{euclid}(u,t)$ とする。$r(u) < d(s,u)$ かつ $r(u) < \text{lb}(u,t)$ の両方が成り立つなら$u$から先の辺の緩和を打ち切ってよい。

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M
x_1 y_1
:
x_N y_N
r_1 ... r_N
s t

制約

$2 \le N \le 2\times10^5$
$1 \le M \le 2\times10^5$
辺重み $\ge$ 直線距離
$r_i$ は正しい到達値

入出力例

入力例1

7 7
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
3 7 13
4 7 13
0 0
10 0
20 0
30 0
40 0
50 0
25 12
0 10 20 20 10 0 0
1 6

出力例1

50

頂点7(25,12)は"寄り道"でr(7)=0。1→6への最短経路は1-2-3-4-5-6(距離50)で頂点7を経由する必要はなく、探索中に到達しても先を枝刈りできる。

概念図：幹線上の頂点 vs 寄り道の頂点

サンプルの道路網（頂点1〜6が幹線、頂点7が寄り道） 1 2 3 4 5 6 7 r(7)=0（寄り道、常に枝刈り対象） r=0 r=10 r=20 r=20 r=10 r=0 中央の頂点ほど到達値が大きい(幹線)。端点・寄り道は小さい(枝刈りされやすい)

ヒント（段階的開示）

ヒント1（方向性）

道路網には幹線道路と行き止まりに近い横道がある。横道の頂点は近くの地点間の移動でしか使われず、遠く離れたs-t間の最短経路には登場しにくい。この「重要度」を事前に数値化しておければ探索時に切り捨てられるはずである。

ヒント2（アプローチ）

到達値$r(v)$の定義そのものが最短経路上に現れるための必要条件を与える：$v$が$a$-$b$最短経路上にあるなら$r(v)\ge\min(d(a,v),d(v,b))$。対偶を取れば、$d(s,v)$と$t$への下界の両方が$r(v)$を上回っているなら$v$は経路上に現れない。下界にはユークリッド距離（辺重み$\ge$直線距離の前提から安全）を使う。

ヒント3（誘導） 
if u != s and u != t:
    lb = euclid(u, t)
    if reach[u] < d - EPS and reach[u] < lb - EPS:
        continue  # 枝刈り：uから先は展開しない
for v, w in adj[u]:
    # 通常のダイクストラ法の緩和処理

模範解答 (Python)

import sys
import heapq
import math

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = float(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))

    xy = [(0.0, 0.0)] * (N + 1)
    for i in range(1, N + 1):
        x = float(data[idx]); idx += 1
        y = float(data[idx]); idx += 1
        xy[i] = (x, y)

    reach = [0.0] * (N + 1)
    for i in range(1, N + 1):
        reach[i] = float(data[idx]); idx += 1

    s = int(data[idx]); idx += 1
    t = int(data[idx]); idx += 1

    def euclid(a, b):
        ax, ay = xy[a]
        bx, by = xy[b]
        return math.hypot(ax - bx, ay - by)

    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[s] = 0
    visited = [False] * (N + 1)
    pq = [(0.0, s)]
    EPS = 1e-6

    while pq:
        d, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        if u == t:
            break

        if u != s and u != t:
            lb_to_t = euclid(u, t)
            if reach[u] < d - EPS and reach[u] < lb_to_t - EPS:
                continue

        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v] - 1e-9:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    ans = dist[t] if dist[t] < INF else -1
    if ans == -1:
        print(-1)
    else:
        if abs(ans - round(ans)) < 1e-6:
            print(int(round(ans)))
        else:
            print(f"{ans:.4f}")

main()

Step-by-Step 解説

1到達値の定義とその意味
$r(v)=\max\{\min(d(a,v),d(v,b)) \mid v\text{ が } a\text{-}b\text{ 最短経路上}\}$。近い方の端点までの距離は高々$r(v)$という保証。
2下界としてのユークリッド距離
辺重み$\ge$直線距離の前提から$d(v,t)\ge\text{euclid}(v,t)$が安全な下界になる。
3枝刈りの安全性
枝刈りは頂点uの確定は止めず、uからさらに先の辺の緩和だけを止める。uが本当に最短経路上にないなら最終的な$d(s,t)$は変わらない。
4精度に関する注意
$r(u)=\text{lb}(u,t)$の境界ケースでは安全側（枝刈りしない）に倒す必要があり、適切なイプシロンでの厳密な不等号判定が必須。
5計算量
到達値の前処理（本問では入力で与えられる）は重いが、クエリ時は各頂点O(1)のユークリッド距離計算のみで通常のダイクストラ法O(M log N)にほぼ定数倍のオーバーヘッド。

よくあるミス

ミス原因正しい書き方
枝刈り条件をreach[u]<dだけで判定しtへの下界を考慮しない「到達値が始点距離より小さければ切ってよい」と誤解始点側と終点側の両方が同時に満たされて初めて枝刈りできる
境界ケース(到達値と下界がちょうど等しい)で誤って枝刈りする不等号を<=にする、イプシロンの符号や大きさを誤るreach[u] < 値 - EPS のように確実に下回っているときのみ枝刈りし境界は安全側に倒す
sやt自身にも枝刈り条件を適用してしまうu!=s and u!=tのガードを忘れる始点・終点は常に展開するよう明示的に除外する
辺重みとユークリッド距離の大小関係の前提を確認せず適用する下界として使える根拠(辺重み≥直線距離)を無視する幾何的な埋め込みを持つ問題設定でのみこの下界を使う
到達値配列の読み込み順序を頂点番号とずらしてしまう1-indexed/0-indexedの混同reach[1..N]が頂点1..Nに対応するようインデックスを揃える

次のステップ

  • 発展: 到達値そのものを計算するアルゴリズム（全頂点対最短路の近似計算+反復的な低到達値頂点の除去）を実装せよ。
  • 発展2: Reach-based PruningとALT法(Q2)を組み合わせたREALアルゴリズム(Reach + A*)が単体より枝刈り効果が高くなる理由を考察せよ。

自己評価

自分の回答

気づき・メモ