概要

地点1から出発し、指定されたK個の地点をすべて1回以上訪問したのち、地点Nに到着するまでの最小移動時間を求める問題です。

考察

この問題を解くにあたり、まず素朴な考え方として「すべての訪れ方を試す」というものが浮かびます。K個の地点を訪れる順番の総数は \(K!\) 通りですが、Kが最大15であるため \(15! \approx 1.3 \times 10^{12}\) 通りとなり、計算が終わりません。

しかし、Kが最大15であることに着目すると、ビット動的計画法（bitDP）を用いて訪問状態を管理することで \(O(K^2 2^K)\) で順番を探索できることがわかります。

bitDPを行うためには、目的地間の移動時間が必要です。元のグラフ上では、目的地Aから目的地Bへ直接移動せず、他の地点を経由したほうが早い場合があります。したがって、あらかじめ重要な地点同士の最短距離を求めておく必要があります。 この問題における「重要な地点」とは、出発地点（地点1）、K個の届け先、到着地点（地点N）の合計 \(K+2\) 個の地点です。

これら \(K+2\) 個の地点をそれぞれ起点としてダイクストラ法を実行すれば、任意の2つの重要地点間の最短移動時間が求まります。その後、この \(K+2\) 個の地点からなる完全グラフ上でbitDPを行えば、効率よく最小移動時間を計算できます。

アルゴリズム

1. 重要地点のリストアップ: 出発地点（1）、K個の届け先（\(C_1, \dots, C_K\)）、到着地点（N）をリストに格納します。このリストのインデックスを \(0\) から \(K+1\) とします。
2. 最短距離の計算: 各重要地点を始点としてダイクストラ法を実行し、すべての地点への最短距離を求めます。これを用いて、重要地点同士の最短距離テーブル dist_matrix を作成します。
3. bitDPによる経路探索:
   • 状態 dp[i][S] を「現在すでに訪れた届け先の集合が \(S\)（ビット列で表現）であり、最後に訪れた届け先が \(i\)（0-indexed）であるときの、出発地点からの最小移動時間」と定義します。
   • 初期状態として、出発地点から各届け先 \(i\) へ直接向かう場合の距離 dist_matrix[0][i+1] を dp[i][1 << i] に代入します。
   • 各状態 dp[i][S] から、まだ訪れていない届け先 \(j\) へ移動する遷移を行い、dp[j][S | (1 << j)] の値を更新します。
4. 答えの算出: すべての届け先を訪れた状態（\(S = 2^K - 1\)）から到着地点（N）へ向かう移動時間を足し合わせ、その最小値を答えとして出力します。

計算量

• 時間計算量: \(O((K+2)M \log N + K^2 2^K)\)
  • ダイクストラ法を \(K+2\) 回実行するため \(O((K+2) M \log N)\)
  • bitDPの遷移が \(O(K^2 2^K)\)
  • 制約下では十分に間に合います。
• 空間計算量: \(O(N + K^2)\)
  • グラフの隣接リストが \(O(N+M)\)、距離行列やDPテーブルが \(O(K^2)\) です。

実装のポイント

• 道路の移動時間 \(W_i\) が最大 \(10^9\) であり、移動を繰り返すと合計値が int 型の範囲（約 \(2 \times 10^9\)）を超えるため、距離の管理には long long 型を使用します。

• INF（無限大）の値も、距離の最大値（最大 \(10^5 \times 10^9 = 10^{14}\) 程度）を考慮し、1e18 のように十分大きな値を設定します。

• bitDPのDP配列では届け先のインデックスを \(0 \sim K-1\) として扱いますが、dist_matrix では出発地点を \(0\)、届け先を \(1 \sim K\)、到着地点を \(K+1\) としているため、インデックスのずれ（i+1 のようなオフセット）に注意して実装します。

  ソースコード

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

using namespace std;
typedef long long ll;
const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<vector<pair<int, ll>>> g(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    vector<int> C(K);
    for (int i = 0; i < K; i++) {
        cin >> C[i];
    }

    auto dijkstra = [&](int s) {
        vector<ll> dist(N + 1, INF);
        dist[s] = 0;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if (d > dist[v]) continue;
            for (auto [to, w] : g[v]) {
                if (dist[to] > d + w) {
                    dist[to] = d + w;
                    pq.push({dist[to], to});
                }
            }
        }
        return dist;
    };

    vector<int> node_to_v(K + 2);
    node_to_v[0] = 1;
    for (int i = 0; i < K; i++) node_to_v[i + 1] = C[i];
    node_to_v[K + 1] = N;

    vector<vector<ll>> dist_matrix(K + 2, vector<ll>(K + 2, INF));

    vector<vector<ll>> dijkstra_results(K + 2);
    for (int i = 0; i < K + 2; i++) {
        dijkstra_results[i] = dijkstra(node_to_v[i]);
    }

    for (int i = 0; i < K + 2; i++) {
        for (int j = 0; j < K + 2; j++) {
            dist_matrix[i][j] = dijkstra_results[i][node_to_v[j]];
        }
    }

    vector<vector<ll>> dp(K, vector<ll>(1 << K, INF));
    for (int i = 0; i < K; i++) {
        dp[i][1 << i] = dist_matrix[0][i + 1];
    }

    for (int S = 0; S < (1 << K); S++) {
        for (int i = 0; i < K; i++) {
            if (!(S & (1 << i))) continue;
            if (dp[i][S] == INF) continue;
            for (int j = 0; j < K; j++) {
                if (S & (1 << j)) continue;
                int next_S = S | (1 << j);
                ll cost = dp[i][S] + dist_matrix[i + 1][j + 1];
                if (dp[j][next_S] > cost) {
                    dp[j][next_S] = cost;
                }
            }
        }
    }

    ll ans = INF;
    int full_S = (1 << K) - 1;
    for (int i = 0; i < K; i++) {
        ll cost = dp[i][full_S] + dist_matrix[i + 1][K + 1];
        if (ans > cost) {
            ans = cost;
        }
    }

    cout << ans << "\n";

    return 0;
}

この解説は or-glm5.2-high によって生成されました。