概要

本問題は、与えられたグラフ上で、始点 \(1\) から出発して指定された \(K\) 個の地点をすべて訪問し、最終的に終点 \(N\) に到達するまでの最短経路長を求める問題です。

訪れるべき地点の数 \(K\) が最大でも \(15\) と非常に小さいことに着目し、ダイクストラ法による地点間の最短距離計算と、ビットDP（動的計画法）による巡回ルートの最適化を組み合わせることで、高速に解くことができます。

---

考察

1. 愚直なアプローチとその限界

すべての地点の間の最短距離を求めるために、全点対最短経路アルゴリズム（ワーシャル・フロイド法など）を使用すると、時間計算量が \(O(N^3)\) となり、 \(N \le 10^5\) の制約下では実行時間制限に間に合いません。

しかし、この問題で自由に順番を決めて巡回する必要があるのは、始点 \(1\)、終点 \(N\)、および \(K\) 個の届け先のみです。これらの重要な地点（以下、「代表点」と呼びます）の数は高々 \(K + 2 \le 17\) 個しかありません。

したがって、すべての頂点間の距離を求める必要はなく、代表点から他の代表点への最短距離だけが分かれば十分です。

2. ダイクストラ法の活用

代表点の数が少ないため、各代表点を始点としたダイクストラ法を個別に実行することで、必要な地点間の最短距離を効率的に求めることができます。 具体的には、始点 \(1\) と \(K\) 個の届け先の計 \(K + 1\) 箇所からダイクストラ法を実行します（終点 \(N\) から出発する必要はないため、終点からのダイクストラ法は不要です）。

これにより、任意の代表点ペア間の最短距離を保持する、サイズ \((K+2) \times (K+2)\) の隣接行列のような距離テーブル dist を作成できます。

3. ビットDPによるルートの最適化

距離テーブルが完成した後は、問題は「巡回セールスマン問題（TSP）」の変種に帰着されます。 \(K \le 15\) であるため、訪問済みの届け先の集合をビット（ \(2^K\) 通りの状態）で表すビットDPを用いることで、すべての届け先を巡る最適な順番を高速に探索できます。

---

アルゴリズム

ステップ1: 代表点の整理

始点 \(1\)、届け先 \(C_1, \dots, C_K\)、終点 \(N\) を一つの配列 targets にまとめます。 - targets[0] = 1 （始点） - targets[1] 〜 targets[K] \(= C_1, \dots, C_K\) （届け先） - targets[K+1] = N （終点）

ステップ2: 代表点間の最短距離の計算

各 \(i\) (\(0 \le i \le K\)) について、targets[i] を始点としたダイクストラ法を実行します。 得られた最短距離から、距離テーブル dist[i][j] （代表点 \(i\) から代表点 \(j\) への最短距離）を構築します。

ステップ3: ビットDPの実行

以下のようなDPテーブルを定義します。 - dp[S][u]：これまでに訪問した届け先の集合が \(S\)（ \(K\) ビットの整数）であり、最後に訪れた届け先が \(u\) （\(1 \le u \le K\)）であるときの、始点 \(1\) からの最小移動時間。

1. 初期化

最初に訪れる届け先 \(j\) （\(0 \le j < K\)）について、始点 \(1\) （代表点 \(0\)）からの距離で初期化します。 $\(dp[2^j][j + 1] = dist[0][j + 1]\)$ その他の状態は無限大（INF）で初期化します。

2. 遷移

現在の訪問状態 \(S\) と最後に訪れた届け先 \(u\)（代表点 \(u+1\)）から、まだ訪れていない届け先 \(v\)（代表点 \(v+1\)）へ移動する遷移を考えます。 \(v\) が \(S\) に含まれていない（\(S\) の \(v\) 番目のビットが \(0\)）とき、新しい状態 \(next\_S = S \cup \{v\}\) への遷移は以下のようになります。 $\(dp[next\_S][v + 1] = \min(dp[next\_S][v + 1], dp[S][u + 1] + dist[u + 1][v + 1])\)$

3. 答えの導出

すべての届け先を訪問した状態は \(S = 2^K - 1\) です。ここから最後に終点 \(N\) （代表点 \(K+1\)）へ向かうため、求める最小値は以下のようになります。 $\(\min_{0 \le u < K} \left( dp[2^K - 1][u + 1] + dist[u + 1][K + 1] \right)\)$

---

計算量

時間計算量

• ダイクストラ法: \(K + 1\) 回実行します。1回あたり \(O((N + M) \log N)\) かかるため、全体で \(O(K(N + M) \log N)\) です。
• ビットDP: 状態数が \(2^K \times K\) であり、各状態からの遷移数が \(K\) 通りであるため、全体で \(O(2^K \cdot K^2)\) です。

よって、総時間計算量は \(O(K(N + M) \log N + 2^K \cdot K^2)\) となります。 制約の \(N \le 10^5, M \le 5 \times 10^4, K \le 15\) を代入すると、全体の計算回数は約 \(5 \times 10^7\) 回となり、実行時間制限（通常2〜3秒）に十分間に合います。

空間計算量

• グラフの隣接リスト: \(O(N + M)\)
• 距離テーブル dist: \(O(K^2)\)
• DPテーブル dp: \(O(2^K \cdot K)\)

よって、総空間計算量は \(O(N + M + 2^K \cdot K)\) となり、メモリ制限に対しても非常に余裕があります。

---

実装のポイント

• インデックスの対応付け: 元のグラフの頂点番号（ \(1\) 〜 \(N\) ）と、DPで用いる代表点のインデックス（ \(0\) 〜 \(K+1\) ）を混同しないように設計されています。正解コードでは targets 配列を介してこれらを正しく管理しています。

• 型とオーバーフローへの対策: 移動距離の合計は最大で \(10^9 \times 10^5 = 10^{14}\) 程度に達する可能性があるため、距離を表す型には long long を使用し、未到達を表す無限大 INF には 1e18 などの十分に大きな値を使用しています。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long cost;
};

int N, M, K;
vector<vector<Edge>> adj;
vector<int> targets;
vector<vector<long long>> dist;

void dijkstra(int start_idx, int start_node) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    vector<long long> d(N + 1, INF);
    d[start_node] = 0;
    pq.push({0, start_node});
    
    while (!pq.empty()) {
        auto [cd, u] = pq.top();
        pq.pop();
        
        if (cd > d[u]) continue;
        
        for (const auto& edge : adj[u]) {
            if (d[edge.to] > d[u] + edge.cost) {
                d[edge.to] = d[u] + edge.cost;
                pq.push({d[edge.to], edge.to});
            }
        }
    }
    
    for (int i = 0; i < (int)targets.size(); ++i) {
        dist[start_idx][i] = d[targets[i]];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (!(cin >> N >> M >> K)) return 0;
    
    adj.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    targets.resize(K + 2);
    targets[0] = 1;
    for (int i = 1; i <= K; ++i) {
        cin >> targets[i];
    }
    targets[K + 1] = N;
    
    dist.assign(K + 2, vector<long long>(K + 2, INF));
    for (int i = 0; i <= K; ++i) {
        dijkstra(i, targets[i]);
    }
    
    vector<vector<long long>> dp(1 << K, vector<long long>(K + 1, INF));
    for (int j = 0; j < K; ++j) {
        dp[1 << j][j + 1] = dist[0][j + 1];
    }
    
    for (int s = 1; s < (1 << K); ++s) {
        for (int u = 0; u < K; ++u) {
            if (!(s & (1 << u))) continue;
            if (dp[s][u + 1] == INF) continue;
            
            for (int v = 0; v < K; ++v) {
                if (!(s & (1 << v))) {
                    int next_s = s | (1 << v);
                    if (dp[next_s][v + 1] > dp[s][u + 1] + dist[u + 1][v + 1]) {
                        dp[next_s][v + 1] = dp[s][u + 1] + dist[u + 1][v + 1];
                    }
                }
            }
        }
    }
    
    long long ans = INF;
    for (int u = 0; u < K; ++u) {
        if (dp[(1 << K) - 1][u + 1] != INF && dist[u + 1][K + 1] != INF) {
            ans = min(ans, dp[(1 << K) - 1][u + 1] + dist[u + 1][K + 1]);
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。