Day 118-Q3 — 縮約階層法（Contraction Hierarchies）

問題

N頂点M辺の無向重み付きグラフが与えられる。Q個のクエリがあり、各クエリは頂点$s,t$が与えられるので、$s$から$t$までの最短距離を出力せよ（到達不能なら-1、$s=t$なら0）。

入力形式

N M
u_1 v_1 w_1
...
u_M v_M w_M
Q
s_1 t_1
...
s_Q t_Q

制約

入出力例

5 6
1 2 4
2 3 1
1 3 2
3 4 5
4 5 3
2 5 10
3
1 5
1 4
2 4

10
7
6

1→5: 1→3→4→5 = 2+5+3=10 が最短。1→4: 1→3→4=2+5=7。2→4: 2→3→4=1+5=6。

概念図: 縮約とショートカット辺、双方向クエリ

ヒント（段階的開示）

# 縮約フェーズ(前処理):
# 1. 現在アクティブな頂点集合から次数最小の頂点vを選ぶ(重要度の低い頂点を先に消す簡易ヒューリスティック)
# 2. vの隣接頂点対(u,w)ごとに、候補ショートカット重み cand = weight(u,v)+weight(v,w) を計算
# 3. vを除いたグラフでuからwへの最短距離(ウィットネス距離)を求め、それがcand以下ならショートカット不要
# 4. そうでなければ u-w 間にショートカット辺(重みcand)を追加する
# 5. vをアクティブ集合から除外し、rank[v] = 縮約した順番
#
# クエリフェーズ:
# forward: sから、rank[隣接頂点] > rank[現在頂点] の辺だけをたどるダイクストラ
# backward: tから同様に(無向グラフなので同じ辺集合)
# 答え = min( distF[x] + distB[x] ) を全頂点xについて調べる

模範解答 (Python)

📋 コピーimport sys
import heapq

INF = float('inf')


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

    active_adj = {i: {} for i in range(1, N + 1)}
    all_edges = {}
    for _ in range(M):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        if b in active_adj[a] and active_adj[a][b] <= w:
            continue
        active_adj[a][b] = w
        active_adj[b][a] = w
        key = (min(a, b), max(a, b))
        if key not in all_edges or all_edges[key] > w:
            all_edges[key] = w

    def witness_dist(src, dst, exclude, limit):
        dist = {src: 0}
        pq = [(0, src)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist.get(u, INF):
                continue
            if d > limit:
                break
            if u == dst:
                return d
            for v, w in active_adj[u].items():
                if v == exclude:
                    continue
                nd = d + w
                if nd > limit:
                    continue
                if nd < dist.get(v, INF):
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        return dist.get(dst, INF)

    active = set(range(1, N + 1))
    rank = [0] * (N + 1)
    order = 0
    while active:
        v = min(active, key=lambda x: (len(active_adj[x]), x))
        rank[v] = order
        order += 1
        neighbors = list(active_adj[v].items())
        for i in range(len(neighbors)):
            u, wu = neighbors[i]
            for j in range(i + 1, len(neighbors)):
                w_, ww = neighbors[j]
                cand = wu + ww
                wd = witness_dist(u, w_, v, cand)
                if wd <= cand:
                    continue
                if w_ not in active_adj[u] or active_adj[u][w_] > cand:
                    active_adj[u][w_] = cand
                    active_adj[w_][u] = cand
                key = (min(u, w_), max(u, w_))
                if key not in all_edges or all_edges[key] > cand:
                    all_edges[key] = cand
        for u, _ in neighbors:
            active_adj[u].pop(v, None)
        del active_adj[v]
        active.discard(v)

    ch_adj = {i: {} for i in range(1, N + 1)}
    for (a, b), w in all_edges.items():
        ch_adj[a][b] = w
        ch_adj[b][a] = w

    def query(s, t):
        if s == t:
            return 0
        distF = {s: 0}
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > distF.get(u, INF):
                continue
            for v, w in ch_adj[u].items():
                if rank[v] <= rank[u]:
                    continue
                nd = d + w
                if nd < distF.get(v, INF):
                    distF[v] = nd
                    heapq.heappush(pq, (nd, v))
        distB = {t: 0}
        pq = [(0, t)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > distB.get(u, INF):
                continue
            for v, w in ch_adj[u].items():
                if rank[v] <= rank[u]:
                    continue
                nd = d + w
                if nd < distB.get(v, INF):
                    distB[v] = nd
                    heapq.heappush(pq, (nd, v))
        best = INF
        for x, dv in distF.items():
            if x in distB:
                best = min(best, dv + distB[x])
        return best if best < INF else -1

    Q = int(data[idx]); idx += 1
    out = []
    for _ in range(Q):
        s = int(data[idx]); idx += 1
        t = int(data[idx]); idx += 1
        out.append(str(query(s, t)))
    print('\n'.join(out))


solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 頂点順序のヒューリスティックを「次数」だけでなく「edge difference（縮約で増える辺数-減る辺数）」で選ぶとより効率的なCHが得られる。
• 次回予告: フィボナッチ進数（Zeckendorf表現）上の桁DP

自己評価

自分の回答

気づき・メモ