Overview

This problem asks us to find the minimum time to start from location \(1\), visit all \(K\) specified delivery destinations, and arrive at location \(N\).

Since \(K \leq 15\) is small, we can first find the “shortest distances between important locations” and then optimize the visiting order using bitmask DP.

Analysis

Although the total number of vertices in the graph is large (\(N \leq 10^5\)), the number of locations we must visit is at most \(15\).

Only the following locations are important:

• Starting location \(1\)
• Delivery destinations \(C_1, C_2, \dots, C_K\)
• Destination \(N\)

We will collectively refer to these as “important locations.”

During delivery, we can freely pass through locations other than the destinations.
Therefore, when moving from one important location to another, we only need to know the shortest distance between them on the original graph.

For example, if there are \(3\) destinations \(A, B, C\), the visiting orders we should consider are:

• \(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\)

and so on.

However, simply trying all permutations would result in \(K!\) possibilities.
When \(K = 15\), \(15!\) is extremely large and will exceed the time limit.

To solve this, we can use bitmask DP, where the set of visited destinations is represented as a bitmask.
By recording the last visited destination for each of the \(2^K\) subsets, we can efficiently find the minimum time.

Additionally, since all edge weights (road lengths) are positive, the shortest distances between important locations can be found using Dijkstra’s algorithm.

Algorithm

First, we arrange the important locations as follows:

• points[0] = 1
• points[1] to points[K] are the destinations
• points[K+1] = N

There are \(K+2\) important locations in total.

1. Find the Shortest Distances Between Important Locations

We run Dijkstra’s algorithm starting from each important location.

From the results, we obtain:

\[ dist[i][j] = \text{shortest distance from } points[i] \text{ to } points[j] \]

This allows us to treat the original large graph as a complete graph consisting only of the important locations.

2. Determine the Visiting Order Using Bitmask DP

We define the DP state as follows:

\[ dp[mask][i] \]

represents the minimum travel time when:

• The set of visited destinations is mask
• The last visited destination is \(i\)

Here, \(i\) represents the destination using \(0\)-indexed notation.
In other words, destination \(C_i\) corresponds to points[i+1].

Initialization

Initially, we travel directly from location \(1\) to each destination:

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

Transitions

Suppose we are currently at destination \(i\) (the last visited) and we want to visit an unvisited destination \(j\) next.

With

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

we update:

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

Answer

Let the state where all destinations have been visited be

\[ full = 2^K - 1 \]

If the last visited destination is \(i\), we must travel from there to location \(N\).

Therefore, the answer is:

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

Complexity

• Time Complexity: \(O((K+2)(N+M)\log N + 2^K K^2)\)
• Space Complexity: \(O(N+M + (K+2)^2 + 2^K K)\)

Since \(K \leq 15\), \(2^K K^2\) can be computed well within the time limit.

Implementation Details

Since distances can become very large in Dijkstra’s algorithm, we should use long long.

The edge weights (road lengths) can be up to \(10^9\), and the number of roads we traverse can also be large, which may cause integer overflow if we use int.

Also, INF should be set to a sufficiently large value, such as:

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

Note that the index of the destination \(i\) in the DP state is shifted relative to its index in the points array:

• Destination \(i\) in the DP corresponds to points[i+1] in the actual important locations array.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-high.