概要

営業所 \(S\) から出発して \(K(\le 15)\) 個の配達先をすべて訪問し、再び \(S\) に戻る最小移動時間を求める問題です。
「グラフ上の巡回（TSP）」を、配達先が少ないことを利用して解きます。

考察

重要な気づき

• 道路ネットワークは \(N\le 10^4, M\le 2\times 10^4\) と大きいですが、訪れるべき地点は \(S\) と配達先 \(K\) 個の合計 \(K+1\le 16\) 個しかないのがポイントです。
• 配達順は自由なので、結局やりたいことは
  「\(S\) と配達先だけを頂点とする完全グラフ」を作り、その上で最短巡回を求める
  ことに近いです。

素朴な方法がダメな理由

• 配達順を全列挙すると \(K!\) 通り。\(K=15\) なら \(15!\approx 1.3\times 10^{12}\) で不可能です（TLE）。
• また、順番を決めるたびに「次の目的地までの最短路」を元の大きいグラフで都度探索すると、さらに重くなります。

解決方針

1. まず、必要な地点（\(S\) と配達先）同士の最短距離だけを集める
   → 各地点からダイクストラ法を実行して距離表を作る。
2. その距離表を使って、配達先 \(K\) 個に対する巡回問題を
   bitDP（巡回セールスマン問題の典型DP）で解く。

例：配達先が 3 件（A,B,C）なら、
「S→A→C→B→S」などの順序を直接全列挙せず、
「今どこまで訪問したか（集合）」と「最後にいる配達先」を状態にして最小値を更新します。

アルゴリズム

1. 距離表の作成（ダイクストラ）

• 対象地点 terminals = [S] + D（サイズ \(t=K+1\)）を用意。
• 各 terminals[i] を始点にダイクストラ法を行い、元グラフ上の最短距離 dist を得る。
• 距離表 dist_mat[i][j] = dist[terminals[j]] を埋める。
  これで「必要な地点間の移動コスト」だけが取り出せます。

2. bitDP で最短巡回（TSP）

• 配達先を \(1..K\) 番、営業所を \(0\) 番（terminals[0]=S）とします。
• 状態：
  • mask：どの配達先を訪れたかを表すビット集合（サイズ \(2^K\)）
  • last：最後にいる配達先（\(1..K\)）
• DP定義：
  • \(dp[mask][last] =\)
    「集合 mask の配達先をすべて訪れ、最後が last であるときの最小時間」
• 初期化：
  • 最初に 1 件だけ行く場合
    \(dp[1<<(i-1)][i] = dist\_mat[0][i]\)
• 遷移：
  • 次に行く配達先 nxt を選ぶ
    \(dp[mask\cup\{nxt\}][nxt] = \min(dp[mask\cup\{nxt\}][nxt],\ dp[mask][last] + dist\_mat[last][nxt])\)
• 答え：
  • 全部訪問した full = (1<<K)-1 から営業所へ戻る
    \(\min_{last} \left(dp[full][last] + dist\_mat[last][0]\right)\)

計算量

• 時間計算量:
  
  • ダイクストラを \(K+1\) 回：\(O((K+1)\, M \log N)\)
    
  • bitDP：\(O(2^K \cdot K^2)\)
    よって全体で \(O((K+1)\, M \log N + 2^K K^2)\)
• 空間計算量:
  
  • グラフ：\(O(N+M)\)
    
  • 距離配列（ダイクストラ用）：\(O(N)\)（ただしコードでは各始点の dist を保持し、合計 \(O((K+1)N)\)）
    
  • DP：\(O(2^K \cdot K)\)
    よって概ね \(O(N+M + (K+1)N + 2^K K)\)

実装のポイント

• 頂点数が大きいので、最短距離は必ずダイクストラ法（優先度付きキュー）を使います（辺重みが正）。

• bitDP の mask は「配達先のみ」を管理し、営業所 \(S\) は含めない設計にすると実装が簡潔です。

• 距離は最大で大きくなり得るため、INF = 10**30 のように十分大きい値を使います。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読むと高速です。

  ソースコード

import sys
import heapq

def dijkstra(start, g, n):
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[start] = 0
    hq = [(0, start)]
    push = heapq.heappush
    pop = heapq.heappop
    while hq:
        d, v = pop(hq)
        if d != dist[v]:
            continue
        for to, w in g[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                push(hq, (nd, to))
    return dist

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it); v = next(it); w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))

    S = next(it)
    K = next(it)
    D = [next(it) for _ in range(K)]

    terminals = [S] + D  # index 0 is S, 1..K are deliveries
    t = K + 1

    dist_mat = [[0] * t for _ in range(t)]
    all_dists = []
    for s in terminals:
        all_dists.append(dijkstra(s, g, N))
    for i in range(t):
        di = all_dists[i]
        for j in range(t):
            dist_mat[i][j] = di[terminals[j]]

    INF = 10**30
    size = 1 << K
    dp = [[INF] * (K + 1) for _ in range(size)]
    for i in range(1, K + 1):
        dp[1 << (i - 1)][i] = dist_mat[0][i]

    for mask in range(size):
        row = dp[mask]
        for last in range(1, K + 1):
            cur = row[last]
            if cur >= INF:
                continue
            for nxt in range(1, K + 1):
                bit = 1 << (nxt - 1)
                if mask & bit:
                    continue
                nm = mask | bit
                val = cur + dist_mat[last][nxt]
                if val < dp[nm][nxt]:
                    dp[nm][nxt] = val

    full = size - 1
    ans = INF
    for last in range(1, K + 1):
        val = dp[full][last] + dist_mat[last][0]
        if val < ans:
            ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。