Overview

This problem asks us to find the shortest path length on a given graph, starting from the start vertex \(1\), visiting all \(K\) specified destinations, and finally reaching the end vertex \(N\).

By focusing on the fact that the number of destinations to visit, \(K\), is extremely small (\(K \le 15\)), we can solve this problem efficiently by combining shortest path calculations between key vertices using Dijkstra’s algorithm with route optimization using Bitmask DP (Dynamic Programming).

---

Analysis

1. Naive Approach and Its Limitations

To find the shortest path between all pairs of vertices, using an all-pairs shortest path algorithm (such as the Floyd-Warshall algorithm) would take \(O(N^3)\) time complexity, which will not run within the time limit under the constraint \(N \le 10^5\).

However, in this problem, the only vertices for which we need to freely determine the visiting order are the start vertex \(1\), the end vertex \(N\), and the \(K\) destinations. The number of these important vertices (hereafter referred to as “key vertices”) is at most \(K + 2 \le 17\).

Therefore, we do not need to find the distances between all pairs of vertices in the graph; it is sufficient to know only the shortest distances from one key vertex to another.

2. Utilizing Dijkstra’s Algorithm

Since the number of key vertices is small, we can efficiently find the required shortest distances between them by running Dijkstra’s algorithm individually with each key vertex as the start vertex. Specifically, we run Dijkstra’s algorithm from a total of \(K + 1\) locations: the start vertex \(1\) and the \(K\) destinations. (There is no need to run Dijkstra’s algorithm from the end vertex \(N\) because we do not start any paths from there).

This allows us to construct a distance table dist of size \((K+2) \times (K+2)\), which acts as an adjacency matrix storing the shortest distances between any pair of key vertices.

3. Route Optimization via Bitmask DP

Once the distance table is constructed, the problem reduces to a variant of the Traveling Salesperson Problem (TSP). Since \(K \le 15\), we can use Bitmask DP, where the set of already visited destinations is represented as a bitmask (with \(2^K\) possible states), to search for the optimal order of visiting all destinations at high speed.

---

Algorithm

Step 1: Organizing Key Vertices

We collect the start vertex \(1\), the destinations \(C_1, \dots, C_K\), and the end vertex \(N\) into a single array targets. - targets[0] = 1 (Start vertex) - targets[1] to targets[K] \(= C_1, \dots, C_K\) (Destinations) - targets[K+1] = N (End vertex)

Step 2: Calculating Shortest Distances Between Key Vertices

For each \(i\) (\(0 \le i \le K\)), run Dijkstra’s algorithm starting from targets[i]. Using the resulting shortest distances, construct the distance table dist[i][j] (the shortest distance from key vertex \(i\) to key vertex \(j\)).

Step 3: Executing Bitmask DP

We define the DP table as follows: - dp[S][u]: The minimum travel time from the start vertex \(1\) when the set of visited destinations is \(S\) (a \(K\)-bit integer) and the last visited destination is \(u\) (\(1 \le u \le K\)).

1. Initialization

For the first destination \(j\) (\(0 \le j < K\)) to be visited, initialize the DP table with the distance from the start vertex \(1\) (key vertex \(0\)): $\(dp[2^j][j + 1] = dist[0][j + 1]\)$ All other states are initialized to infinity (INF).

2. Transitions

Consider transitioning from the current visited state \(S\) and the last visited destination \(u\) (key vertex \(u+1\)) to an unvisited destination \(v\) (key vertex \(v+1\)). If \(v\) is not included in \(S\) (the \(v\)-th bit of \(S\) is \(0\)), the transition to the new state \(next\_S = S \cup \{v\}\) is as follows: $\(dp[next\_S][v + 1] = \min(dp[next\_S][v + 1], dp[S][u + 1] + dist[u + 1][v + 1])\)$

3. Deriving the Answer

The state where all destinations have been visited is represented by \(S = 2^K - 1\). From this state, we head to the final end vertex \(N\) (key vertex \(K+1\)). Thus, the minimum value we seek is: $\(\min_{0 \le u < K} \left( dp[2^K - 1][u + 1] + dist[u + 1][K + 1] \right)\)$

---

Complexity

Time Complexity

• Dijkstra’s Algorithm: Executed \(K + 1\) times. Since each run takes \(O((N + M) \log N)\) time, the total time for this step is \(O(K(N + M) \log N)\).
• Bitmask DP: The number of states is \(2^K \times K\), and there are \(K\) transitions from each state. Thus, the total time for this step is \(O(2^K \cdot K^2)\).

Therefore, the total time complexity is \(O(K(N + M) \log N + 2^K \cdot K^2)\). Substituting the constraints \(N \le 10^5, M \le 5 \times 10^4, K \le 15\), the total number of operations is approximately \(5 \times 10^7\), which easily runs within the time limit (typically 2 to 3 seconds).

Space Complexity

• Graph adjacency list: \(O(N + M)\)
• Distance table dist: \(O(K^2)\)
• DP table dp: \(O(2^K \cdot K)\)

Therefore, the total space complexity is \(O(N + M + 2^K \cdot K)\), which is well within the memory limit.

---

Implementation Points

• Index Mapping: The solution is designed to avoid confusing the vertex numbers in the original graph (\(1\) to \(N\)) with the indices of the key vertices used in the DP (\(0\) to \(K+1\)). In the correct implementation, these are managed properly via the targets array.

• Data Types and Overflow Prevention: Since the sum of the travel distances can reach up to approximately \(10^9 \times 10^5 = 10^{14}\), we use long long for types representing distances, and a sufficiently large value like 1e18 for INF to represent unreachable states.

  Source Code

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

---

This editorial was generated by gemini-3.5-flash-high.