公式

E - 配達員の巡回 / Delivery Person's Round 解説 by admin

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 によって生成されました。