概要

この問題は、グラフ上の複数の指定された頂点を最短時間で巡回し、最後に始点に戻る経路の最小コストを求めるものです。いわゆる「巡回セールスマン問題（TSP）」の変形です。

考察

まず、この問題は単純な全探索では解けません。なぜなら、配達先の数 \(K\) が最大 \(15\) であり、その訪問順序の組み合わせは \(K!\) 通りあり、それに加えて各移動には最短経路を求めなければならないため、非常に計算量が多くなります。

しかし、注目すべき制約があります： - グラフの頂点数 \(N\) は最大 \(10\,000\)、辺数 \(M\) は最大 \(20\,000\) - しかし、実際に考慮すべきなのは 営業所 と 配達先 の \(K+1\) 点だけです。

したがって、以下の手順で効率的に解くことができます： 1. 営業所 \(S\) とすべての配達先 \(D_1, ..., D_K\) の間の最短距離を前もって計算しておく（全点対最短距離）。 2. この \(K+1\) 点だけの距離情報を用いて、訪問順序を最適化する。これは典型的なビットDPによるTSPの解法が適用できます。

このようにして、グラフ全体ではなく必要な頂点間の最短距離だけを扱うことで、計算量を大幅に削減できます。

アルゴリズム

解法は以下のステップに分かれます：

1. 最短距離の前計算（ダイクストラ法）

• 営業所 \(S\) と各配達先 \(D_j\) を含む合計 \(K+1\) 点について、それぞれを始点としたダイクストラ法を実行。
• これにより、任意の2点間の最短移動時間を前もって求めることができる。

2. 巡回セールスマン問題（TSP）の解法（ビットDP）

• \(dp[mask][i]\)：訪問済みの配達先集合が \(mask\) で、最後に訪れた場所が \(i\) （0は営業所、1〜Kは配達先）のときの最小コスト。
• 初期状態：\(dp[0][0] = 0\)
• 遷移：未訪問の配達先 \(j\) に対して $\( dp[mask \cup \{j\}][j] = \min(dp[mask \cup \{j\}][j],\ dp[mask][i] + \text{cost}(i \to j)) \)$
• 最後に、最後に訪れた頂点から営業所に戻るコストを足して答えを更新。

このようにして、すべての配達先を訪問して戻ってくる最小コストを求めます。

計算量

• ダイクストラ法の実行回数：\(K+1\) 回
• 1回のダイクストラの計算量：\(O(M \log N)\)
• ビットDPの状態数：\(O(2^K \cdot K)\)
• ビットDPの遷移：各状態から \(K\) 回の遷移があるため、\(O(2^K \cdot K^2)\)

したがって、

• 時間計算量: \(O((K+1) \cdot M \log N + 2^K \cdot K^2)\)
• 空間計算量: \(O(N + M + 2^K \cdot K)\)

実装のポイント

• ダイクストラ法は隣接リストで実装し、優先度付きキューを使うことで高速化。
• ビットDPでは、訪問状態をビットマスクで表現し、最後に訪れた場所のインデックスと共に管理する。
• 配達先のインデックスを1-originで扱っているため、配列アクセス時に注意（例：dp[mask][j+1]）。
• 最後に営業所に戻る処理を忘れずに。

## ソースコード

```python
import heapq
from itertools import permutations
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]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    S = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    D = list(map(int, data[idx:idx+K])); idx += K
    
    # 配達先＋営業所のノードリスト
    nodes = [S] + D
    node_index = {node: i for i, node in enumerate(nodes)}
    
    # 全点対最短距離を計算
    dist_all = {}
    for node in nodes:
        dist_all[node] = dijkstra(graph, node, N)
    
    # 配達先間および営業所との距離行列
    # dp[bit][i] := 訪問済み集合bit, 最後に訪れた場所がiのときの最小コスト
    INF = float('inf')
    dp = [[INF] * (K + 1) for _ in range(1 << K)]
    dp[0][0] = 0  # 初期位置は営業所(S)

    # ビットDP
    for mask in range(1 << K):
        for i in range(K + 1):
            if dp[mask][i] == INF:
                continue
            current_node = nodes[i]
            for j in range(K):
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    next_node = D[j]
                    cost = dist_all[current_node][next_node]
                    if dp[next_mask][j + 1] > dp[mask][i] + cost:
                        dp[next_mask][j + 1] = dp[mask][i] + cost

    # 全ての配達先を訪れた後、営業所に戻る
    ans = INF
    full_mask = (1 << K) - 1
    for i in range(K + 1):
        if dp[full_mask][i] != INF:
            last_node = nodes[i]
            return_cost = dist_all[last_node][S]
            ans = min(ans, dp[full_mask][i] + return_cost)
    
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。