概要

地点 \(1\) を出発し、指定された \(K\) 個の届け先をすべて経由して地点 \(N\) に到達するまでの最小移動時間を求める問題です。\(K \leq 15\) という小ささに注目し、最短経路 + 巡回セールスマン問題（bitDP） で解きます。

考察

まず重要な気づきは、「どの届け先をどの順番で回るか」だけが本質的な問題であるという点です。

届け先以外の地点は自由に通過してよいので、ある地点からある地点へ移動するときは、その \(2\) 地点間の最短経路を使えば最適です。つまり、

• 出発地 \(1\)
• 各届け先 \(C_1, C_2, \dots, C_K\)
• 到着地 \(N\)

これら「重要な地点」の間の最短距離さえ分かれば、あとは「どの順番で届け先を訪れるか」を決める問題に帰着できます。

ここで素朴に「届け先の訪問順を全部試す」と \(K!\) 通りの順列を調べることになります。\(K = 15\) では \(15! \approx 1.3 \times 10^{12}\) となり、到底間に合いません。

そこで、訪問順を全列挙する代わりに、「すでに訪れた届け先の集合」と「今いる届け先」 を状態として持つビット DP（巡回セールスマン問題の定石）を使います。これにより計算量を \(O(2^K \cdot K^2)\) まで落とせます。

アルゴリズム

ステップ 1: 重要地点間の最短距離を求める

辺の重みが正なので、ダイクストラ法を使います。

• 地点 \(1\) からの最短距離 distFrom1
• 各届け先 \(C_i\) からの最短距離 distC[i]

これらを求めておけば、

• 「\(1\) から \(C_i\) までの距離」= distFrom1[C[i]]
• 「\(C_i\) から \(C_j\) までの距離」= distC[i][C[j]]
• 「\(C_i\) から \(N\) までの距離」= distC[i][N]

がすべて取り出せます。ダイクストラを実行する回数は \(1 + K\) 回です。

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

dp[mask][i] を次のように定義します。

dp[mask][i] = 地点 \(1\) を出発し、mask で表される集合の届け先をすべて訪問し、最後に届け先 \(i\) にいる ときの最小移動時間

初期化: 最初に届け先 \(i\) を訪れる場合 $\( dp[\,2^i\,][i] = \text{distFrom1}[C_i] \)$

遷移: 集合 mask で最後に \(i\) にいる状態から、まだ訪れていない \(j\) へ移動する $\( dp[\text{mask} \mid 2^j][j] \leftarrow dp[\text{mask}][i] + \text{distC}[i][C_j] \)$

答え: すべての届け先を訪れた状態（full = 全ビットが立った集合）から、最後の届け先 \(i\) を経由して \(N\) へ向かう最小値 $\( \text{ans} = \min_{i} \left( dp[\text{full}][i] + \text{distC}[i][N] \right) \)$

計算量

ダイクストラを \(K+1\) 回実行し、bitDP の遷移を行います。

• 時間計算量: \(O\big((K+1)\,(M \log N) + 2^K \cdot K^2\big)\)
  • ダイクストラ部分: \((K+1)\) 回 × \(O(M \log N)\)
  • bitDP 部分: \(O(2^K \cdot K^2)\)（\(2^{15} \cdot 15^2 \approx 7.4 \times 10^6\) で十分高速）
• 空間計算量: \(O\big((K+1)\,N + 2^K \cdot K\big)\)
  • 各ダイクストラの距離配列と DP テーブル

実装のポイント

• オーバーフローに注意: \(W_i\) は最大 \(10^9\)、経路は複数の辺を含むため、距離の合計は \(64\) ビット整数（long long）で扱う必要があります。INF も加算でオーバーフローしないよう LLONG_MAX/4 程度にしておくと安全です。

• ダイクストラは隣接リスト + 優先度付きキューで実装します。d > dist[u] のときは古い情報なのでスキップする、という枝刈りを忘れないようにしましょう。

• DP の参照は届け先のインデックス \(i\)（\(0\)〜\(K-1\)）と地点番号 \(C_i\) を混同しないように注意します。distC[i] は「\(i\) 番目の届け先からの距離配列」なので、別の届け先 \(C_j\) への距離は distC[i][C[j]] のように地点番号で引きます。

• mask を昇順にループすれば、遷移元の状態が必ず先に確定するため、正しく DP が進みます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    vector<vector<pair<int,long long>>> g(N+1);
    for(int i=0;i<M;i++){
        int u,v; long long w;
        scanf("%d %d %lld", &u, &v, &w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    vector<int> C(K);
    for(int i=0;i<K;i++) scanf("%d", &C[i]);
    
    const long long INF = LLONG_MAX/4;
    
    auto dijkstra = [&](int s)->vector<long long>{
        vector<long long> dist(N+1, INF);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        dist[s]=0;
        pq.push({0,s});
        while(!pq.empty()){
            auto [d,u]=pq.top(); pq.pop();
            if(d>dist[u]) continue;
            for(auto [v,w]:g[u]){
                if(dist[v]>d+w){
                    dist[v]=d+w;
                    pq.push({dist[v],v});
                }
            }
        }
        return dist;
    };
    
    // Dijkstra from node 1
    vector<long long> distFrom1 = dijkstra(1);
    
    // Dijkstra from each delivery point
    vector<vector<long long>> distC(K);
    for(int i=0;i<K;i++) distC[i] = dijkstra(C[i]);
    
    // dist between deliveries
    // dp
    int full = (1<<K)-1;
    vector<vector<long long>> dp(1<<K, vector<long long>(K, INF));
    for(int i=0;i<K;i++){
        dp[1<<i][i] = distFrom1[C[i]];
    }
    for(int mask=0; mask<=full; mask++){
        for(int i=0;i<K;i++){
            if(!(mask&(1<<i))) continue;
            if(dp[mask][i]==INF) continue;
            for(int j=0;j<K;j++){
                if(mask&(1<<j)) continue;
                long long nd = dp[mask][i] + distC[i][C[j]];
                int nmask = mask|(1<<j);
                if(dp[nmask][j] > nd) dp[nmask][j] = nd;
            }
        }
    }
    
    long long ans = INF;
    for(int i=0;i<K;i++){
        if(dp[full][i]==INF) continue;
        ans = min(ans, dp[full][i] + distC[i][N]);
    }
    
    printf("%lld\n", ans);
    return 0;
}

---

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