概要

営業所から出発して \(K\) 個の配達先をすべて回り、再び営業所に戻るときの最短移動時間を求める問題です。\(K \leq 15\) という制約から、巡回セールスマン問題（TSP）をビットマスクDPで解きます。

考察

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

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

重要な気づき

1. グラフ上の最短経路は前処理できる: 実際に巡回順を考えるとき、交差点を1つずつたどる必要はありません。営業所 \(S\) と各配達先 \(D_j\) の間の最短距離さえ分かれば、問題は「\((K+1)\) 個の頂点を巡る TSP」に帰着できます。

2. \(K \leq 15\) はビットマスクDPの合図: 巡回セールスマン問題は NP 困難ですが、頂点数が小さいとき（おおよそ \(20\) 以下）はビットマスクDP で \(O(2^K \cdot K^2)\) で解けます。

解法の流れ

1. \(S\) および \(D_1, D_2, \ldots, D_K\) の合計 \((K+1)\) 個の頂点それぞれを始点としてダイクストラ法を実行し、重要頂点間の最短距離テーブル \(\mathrm{cost}[i][j]\) を作る。
2. ビットマスクDPで、\(S\) を出発して全配達先を回り \(S\) に戻る最短コストを求める。

アルゴリズム

ステップ1: 最短距離テーブルの構築

\(S, D_1, D_2, \ldots, D_K\) の \((K+1)\) 個の頂点それぞれからダイクストラ法を実行します。これにより、任意の2つの重要頂点間の最短距離 \(\mathrm{cost}[i][j]\) が得られます。

例えば \(K=3\), \(S=1\), 配達先が \(\{3, 5, 7\}\) なら、頂点 \(1, 3, 5, 7\) の4つからダイクストラを行い、\(4 \times 4\) の距離テーブルを作ります。

ステップ2: ビットマスクDP（巡回セールスマン問題）

• 状態: \(\mathrm{dp}[\mathrm{mask}][i]\) = 配達先の訪問済み集合が \(\mathrm{mask}\)（ビットで管理）で、現在配達先 \(i\) にいるときの、\(S\) からの最小移動コスト
• 初期状態: \(\mathrm{dp}[1 \ll j][j+1] = \mathrm{cost}[0][j+1]\)（\(S\) から直接配達先 \(j\) に行く）
• 遷移: 訪問済み集合 \(\mathrm{mask}\) で頂点 \(u\) にいるとき、未訪問の頂点 \(v\) へ移動する $\(\mathrm{dp}[\mathrm{mask} \mid (1 \ll (v-1))][v] = \min\left(\mathrm{dp}[\mathrm{mask} \mid (1 \ll (v-1))][v],\; \mathrm{dp}[\mathrm{mask}][u] + \mathrm{cost}[u][v]\right)\)$
• 答え: 全配達先を訪問した状態 \(\mathrm{full\_mask} = 2^K - 1\) から \(S\) に戻るコストの最小値 $\(\mathrm{ans} = \min_{u=1}^{K}\left(\mathrm{dp}[\mathrm{full\_mask}][u] + \mathrm{cost}[u][0]\right)\)$

計算量

• 時間計算量: \(O((K+1) \cdot (N + M) \log N + 2^K \cdot K^2)\)
  • ダイクストラ法を \((K+1)\) 回実行: \(O((K+1)(N + M)\log N)\)
  • ビットマスクDP: \(O(2^K \cdot K^2)\)
  • \(K \leq 15\) なので \(2^{15} \cdot 15^2 \approx 7.4 \times 10^6\) で十分高速
• 空間計算量: \(O(2^K \cdot K + (K+1) \cdot N)\)

実装のポイント

• ノード番号の対応付け: nodes[0] = S, nodes[1..K] = D[0..K-1] として管理し、ビットマスクは配達先のみ（\(K\) ビット）で管理する。\(S\) はビットに含めない。

• ダイクストラの始点: \(S\) と全配達先からそれぞれ実行する必要がある。\(S\) からだけでは配達先同士の最短距離が分からない（グラフが双方向なので \(S\) から各配達先への距離は分かるが、配達先間は別途必要）。

• ビットの対応: 配達先 \(D_j\)（nodes[j+1]）は \(\mathrm{mask}\) の第 \(j\) ビットに対応させる。mask & (1 << (u-1)) で頂点 \(u\)（1-indexed in nodes）が訪問済みかを判定する。

  ソースコード

import heapq
import sys

def dijkstra(graph, start, N):
    dist = [float('inf')] * (N + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (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
    
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    S = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    D = []
    for _ in range(K):
        D.append(int(input_data[idx])); idx += 1
    
    # nodes[0] = S, nodes[1..K] = D[0..K-1]
    nodes = [S] + D
    
    # Dijkstra from each important node
    dist_from = {}
    for node in nodes:
        dist_from[node] = dijkstra(graph, node, N)
    
    # cost[i][j] = shortest distance between nodes[i] and nodes[j]
    num = K + 1  # 0 = S, 1..K = delivery points
    cost = [[0] * num for _ in range(num)]
    for i in range(num):
        for j in range(num):
            cost[i][j] = dist_from[nodes[i]][nodes[j]]
    
    # TSP with bitmask DP
    # State: (mask, i) where mask is subset of {0, 1, ..., K-1} representing visited delivery points
    # i is current position (0 = S, 1..K = delivery points)
    # We need to visit all K delivery points and return to S
    
    full_mask = (1 << K) - 1
    INF = float('inf')
    
    # dp[mask][i] = min cost to have visited delivery points in mask, currently at delivery point i (1-indexed in nodes)
    dp = [[INF] * (K + 1) for _ in range(1 << K)]
    
    # Start from S (node index 0), go to each delivery point
    for j in range(K):
        dp[1 << j][j + 1] = cost[0][j + 1]
    
    for mask in range(1, 1 << K):
        for u in range(1, K + 1):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << (u - 1))):
                continue
            for v in range(1, K + 1):
                if mask & (1 << (v - 1)):
                    continue
                new_mask = mask | (1 << (v - 1))
                nd = dp[mask][u] + cost[u][v]
                if nd < dp[new_mask][v]:
                    dp[new_mask][v] = nd
    
    # Find minimum: visit all, then return to S
    ans = INF
    for u in range(1, K + 1):
        val = dp[full_mask][u] + cost[u][0]
        if val < ans:
            ans = val
    
    print(ans)

if __name__ == '__main__':
    main()

---

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