Official

E - 配達員の巡回 / Delivery Person's Round Editorial by admin Editorial for printing

Claude 4.6 Opus (Thinking)

概要

地点 \(1\) を出発し、\(K\) 個の届け先すべてを訪れて地点 \(1\) に戻る最短経路を求める問題です。\(K \leq 15\) という制約から、巡回セールスマン問題(TSP)をビットマスク DP で解きます。

考察

素朴なアプローチとその問題点

\(K\) 個の届け先を訪れる順番は \(K!\) 通りあります。\(K = 15\) のとき \(15! \approx 1.3 \times 10^{12}\) となり、全列挙は到底間に合いません。

重要な気づき

  1. 中間地点は無視できる: 地点 \(1\) と \(K\) 個の届け先、合わせて \(K+1\) 個の「重要な地点」だけに注目すればよいです。重要な地点間の移動は、元のグラフ上の最短経路で行えばよく、途中の経路は気にする必要がありません。

  2. 距離行列の事前計算: 各重要な地点から Dijkstra 法を実行すれば、重要な地点間の最短距離をすべて求められます。これにより問題は「\((K+1)\) 頂点の完全グラフ上の TSP」に帰着されます。

  3. ビットマスク DP: \(K \leq 15\) なので、「どの届け先を訪問済みか」を \(K\) ビットの整数で表現し、DP で最適な訪問順を求められます。状態数は \(2^K \times (K+1)\) で、\(K=15\) のとき約 \(50\) 万程度です。

アルゴリズム

ステップ 1: 最短距離の前計算

重要な地点は地点 \(1\) と届け先 \(V_1, \ldots, V_K\) の計 \(K+1\) 個です。それぞれの地点を始点として Dijkstra 法を実行し、全頂点への最短距離を求めます。これにより、重要な地点同士の距離行列 \(\text{key\_dist}[i][j]\) が得られます。

ステップ 2: ビットマスク DP による TSP

  • 状態: \(dp[\text{mask}][u]\) = 届け先の訪問状態が \(\text{mask}\) で、現在重要な地点 \(u\) にいるときの最小コスト
  • 初期状態: \(dp[0][0] = 0\)(地点 \(1\) にいて、どの届け先もまだ訪問していない)
  • 遷移: 状態 \((\text{mask}, u)\) から、まだ訪問していない届け先 \(j\) に移動する:

\[dp[\text{mask} \mid (1 \ll j)][j+1] = \min\left(dp[\text{mask} \mid (1 \ll j)][j+1],\; dp[\text{mask}][u] + \text{key\_dist}[u][j+1]\right)\]

  • 答え: 全届け先を訪問した状態 \(\text{full\_mask} = 2^K - 1\) で、地点 \(1\) に戻るコストを加算した最小値:

\[\text{ans} = \min_{u} \left( dp[\text{full\_mask}][u] + \text{key\_dist}[u][0] \right)\]

計算量

  • 時間計算量: \(O((K+1) \cdot (N + M) \log N + 2^K \cdot K^2)\)
    • Dijkstra を \(K+1\) 回実行: \(O((K+1) \cdot (N + M) \log N)\)
    • ビットマスク DP: \(O(2^K \cdot K^2)\)(各状態から最大 \(K\) 個の遷移)
    • \(K = 15, N = M = 5 \times 10^4\) で十分高速
  • 空間計算量: \(O((K+1) \cdot N + 2^K \cdot K)\)
    • Dijkstra の距離配列: \(O((K+1) \cdot N)\)
    • DP テーブル: \(O(2^K \cdot (K+1))\)

実装のポイント

  • 重要な地点のインデックス管理: 地点 \(1\) をインデックス \(0\)、届け先 \(V_i\) をインデックス \(i\)(\(1 \leq i \leq K\))として管理すると、ビットマスクの \(j\) ビット目が届け先 \(V_{j+1}\)(キーノードインデックス \(j+1\))に対応し、混乱を避けられます。

  • 高速入力: Python では sys.stdin.buffer.read() でまとめて読み込むことで、大量入力時の速度を改善できます。

  • 無限大の扱い: 到達不能な状態を float('inf') で初期化し、遷移時にスキップすることで不要な計算を避けます。

    ソースコード

import heapq
import sys

def dijkstra(graph, start, N):
    dist = [float('inf')] * (N + 1)
    dist[start] = 0
    hq = [(0, start)]
    while hq:
        d, u = heapq.heappop(hq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(hq, (nd, v))
    return dist

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    V = []
    for i in range(K):
        V.append(int(input_data[idx])); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    for i in range(M):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    # Key nodes: node 1 (index 0) and V[0..K-1] (indices 1..K)
    key_nodes = [1] + V  # length K+1
    
    # Compute shortest paths from each key node
    # dist_from[i] = shortest distance array from key_nodes[i]
    dist_from = []
    for node in key_nodes:
        dist_from.append(dijkstra(graph, node, N))
    
    # Build distance matrix between key nodes
    # key_dist[i][j] = shortest distance from key_nodes[i] to key_nodes[j]
    num_keys = K + 1
    key_dist = [[0] * num_keys for _ in range(num_keys)]
    for i in range(num_keys):
        for j in range(num_keys):
            key_dist[i][j] = dist_from[i][key_nodes[j]]
    
    # TSP with bitmask DP
    # State: (visited subset of delivery nodes (bits 0..K-1 for V[0]..V[K-1]), current key node index)
    # We need to visit all K delivery nodes and return to node 0 (which is key_nodes[0] = 1)
    
    full_mask = (1 << K) - 1
    INF = float('inf')
    
    # dp[mask][i] = min cost to have visited the delivery nodes in mask, currently at key node i
    # i ranges from 0 to K (0 = node 1, 1..K = delivery nodes)
    dp = [[INF] * num_keys for _ in range(1 << K)]
    
    # Start at key node 0 (node 1), no deliveries done
    dp[0][0] = 0
    
    for mask in range(1 << K):
        for u in range(num_keys):
            if dp[mask][u] == INF:
                continue
            cur_cost = dp[mask][u]
            # Try going to each delivery node
            for j in range(K):
                if mask & (1 << j):
                    continue
                v = j + 1  # key node index for V[j]
                new_mask = mask | (1 << j)
                new_cost = cur_cost + key_dist[u][v]
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost
    
    # Find minimum cost: visit all deliveries then return to node 1
    ans = INF
    for u in range(num_keys):
        if dp[full_mask][u] == INF:
            continue
        total = dp[full_mask][u] + key_dist[u][0]
        if total < ans:
            ans = total
    
    print(ans)

if __name__ == '__main__':
    main()

この解説は claude4.6opus-thinking によって生成されました。

posted:
last update: