概要

地点 \(1\) から出発し、指定された \(K\) 個の届け先をすべて訪問して、地点 \(N\) に到着する最短時間を求める問題です。

\(K \leq 15\) と小さいため、「重要な地点間の最短距離」を先に求め、その上で巡回順を bit DP で最適化します。

考察

グラフ全体の頂点数は \(N \leq 10^5\) と大きいですが、必ず訪れる必要がある地点は高々 \(15\) 個です。

重要なのは次の地点だけです。

• 出発地点 \(1\)
• 届け先 \(C_1, C_2, \dots, C_K\)
• 終点 \(N\)

これらをまとめて「重要地点」と呼ぶことにします。

配送中は届け先以外の地点を自由に通過できます。
したがって、ある重要地点から別の重要地点へ移動するときは、元のグラフ上での最短距離だけ分かれば十分です。

例えば、届け先が \(A, B, C\) の \(3\) 個なら、考えるべき順番は

• \(1 \to A \to B \to C \to N\)
• \(1 \to B \to A \to C \to N\)
• \(1 \to C \to A \to B \to N\)

のような届け先の訪問順です。

ただし、単純に全順列を試すと \(K!\) 通りあります。
\(K = 15\) のとき \(15!\) は非常に大きく、間に合いません。

そこで、届け先の訪問済み集合を bit で管理する bit DP を使います。
\(2^K\) 通りの集合について、最後に訪れた届け先を記録すれば、効率よく最小値を求められます。

また、道路の重みはすべて正なので、重要地点間の最短距離はダイクストラ法で求められます。

アルゴリズム

まず、重要地点を次のように並べます。

• points[0] = 1
• points[1] から points[K] が届け先
• points[K+1] = N

重要地点は全部で \(K+2\) 個です。

1. 重要地点間の最短距離を求める

各重要地点を始点としてダイクストラ法を行います。

その結果から、

\[ dist[i][j] = points[i] から points[j] への最短距離 \]

を求めます。

これにより、元の大きなグラフを、重要地点だけからなる完全グラフのように扱えます。

2. bit DP で届け先を訪れる順番を決める

DP を次のように定義します。

\[ dp[mask][i] \]

を、

• 訪問済み届け先集合が mask
• 最後に訪れた届け先が \(i\)

であるときの最小移動時間とします。

ここで、\(i\) は \(0\)-indexed で届け先を表します。
つまり、届け先 \(C_i\) は points[i+1] に対応します。

初期化

最初は地点 \(1\) から各届け先へ直接向かいます。

\[ dp[1 \ll i][i] = dist[0][i+1] \]

遷移

現在、最後に届け先 \(i\) にいて、次にまだ訪れていない届け先 \(j\) へ行くとします。

\[ nmask = mask \mid (1 \ll j) \]

として、

\[ dp[nmask][j] = \min(dp[nmask][j],\ dp[mask][i] + dist[i+1][j+1]) \]

と更新します。

答え

すべての届け先を訪問した状態を

\[ full = 2^K - 1 \]

とします。

最後に訪れた届け先を \(i\) とすると、そこから地点 \(N\) へ向かう必要があります。

したがって答えは、

\[ \min_i \left(dp[full][i] + dist[i+1][K+1]\right) \]

です。

計算量

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

\(K \leq 15\) なので、\(2^K K^2\) は十分高速に計算できます。

実装のポイント

ダイクストラ法では距離が大きくなる可能性があるため、long long を使います。

道路の重みは最大 \(10^9\) で、通る道路数も多くなり得るため、int ではオーバーフローする可能性があります。

また、INF は十分大きな値として、

const ll INF = (1LL << 62);

のように設定しています。

DP の添字では、届け先 \(i\) と points の添字がずれている点に注意が必要です。

• DP 上の届け先 \(i\)
• 実際の重要地点配列では points[i+1]

に対応します。

ソースコード

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

using ll = long long;

struct Edge {
    int to;
    ll w;
};

const ll INF = (1LL << 62);

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

    int N, M, K;
    cin >> N >> M >> K;

    vector<vector<Edge>> graph(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

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

    vector<int> points;
    points.push_back(1);
    for (int c : C) points.push_back(c);
    points.push_back(N);

    int P = K + 2;
    vector<vector<ll>> dist(P, vector<ll>(P, INF));

    auto dijkstra = [&](int s) {
        vector<ll> d(N + 1, INF);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

        d[s] = 0;
        pq.push({0, s});

        while (!pq.empty()) {
            auto [cur, v] = pq.top();
            pq.pop();

            if (cur != d[v]) continue;

            for (auto e : graph[v]) {
                if (d[e.to] > cur + e.w) {
                    d[e.to] = cur + e.w;
                    pq.push({d[e.to], e.to});
                }
            }
        }

        return d;
    };

    for (int i = 0; i < P; i++) {
        vector<ll> d = dijkstra(points[i]);
        for (int j = 0; j < P; j++) {
            dist[i][j] = d[points[j]];
        }
    }

    int S = 1 << K;
    vector<vector<ll>> dp(S, vector<ll>(K, INF));

    for (int i = 0; i < K; i++) {
        dp[1 << i][i] = dist[0][i + 1];
    }

    for (int mask = 0; mask < S; mask++) {
        for (int i = 0; i < K; i++) {
            if (dp[mask][i] == INF) continue;

            for (int j = 0; j < K; j++) {
                if (mask & (1 << j)) continue;

                int nmask = mask | (1 << j);
                dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + dist[i + 1][j + 1]);
            }
        }
    }

    ll ans = INF;
    int full = S - 1;

    for (int i = 0; i < K; i++) {
        ans = min(ans, dp[full][i] + dist[i + 1][K + 1]);
    }

    cout << ans << '\n';

    return 0;
}

---

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