Overview

This problem asks us to find the minimum travel time to start at vertex \(1\), visit all \(K\) specified destinations, and finally reach vertex \(N\). Focusing on the small constraint \(K \leq 15\), we can solve this using shortest paths + Traveling Salesperson Problem (bitDP).

Analysis

First, a crucial observation is that the only essential problem is “in what order to visit the destinations”.

Since we can freely pass through any vertices other than the destinations, when moving from one vertex to another, it is always optimal to use the shortest path between those two vertices. That is, if we know the shortest distances between:

• Starting vertex \(1\)
• Each destination \(C_1, C_2, \dots, C_K\)
• Destination vertex \(N\)

Once we know the shortest distances between these “important vertices”, the problem reduces to deciding the order in which to visit the destinations.

If we naively try all possible visiting orders, we would have to examine \(K!\) permutations. For \(K = 15\), \(15! \approx 1.3 \times 10^{12}\), which is far too slow to run within the time limit.

Therefore, instead of enumerating all permutations, we can use Bit DP (a standard technique for the Traveling Salesperson Problem) where the state is represented by “the set of already visited destinations” and “the current destination”. This reduces the time complexity to \(O(2^K \cdot K^2)\).

Algorithm

Step 1: Find Shortest Distances Between Important Vertices

Since the edge weights are positive, we can use Dijkstra’s algorithm.

• Shortest distance from vertex \(1\): distFrom1
• Shortest distance from each destination \(C_i\): distC[i]

By computing these, we can retrieve:

• “Distance from \(1\) to \(C_i\)” = distFrom1[C[i]]
• “Distance from \(C_i\) to \(C_j\)” = distC[i][C[j]]
• “Distance from \(C_i\) to \(N\)” = distC[i][N]

We only need to run Dijkstra’s algorithm \(1 + K\) times in total.

Step 2: Bit DP (Traveling Salesperson Problem)

We define dp[mask][i] as follows:

dp[mask][i] = The minimum travel time to start at vertex \(1\), visit all destinations in the set represented by mask, and end up at destination \(i\).

Initialization: When visiting destination \(i\) first $\( dp[\,2^i\,][i] = \text{distFrom1}[C_i] \)$

Transition: Moving from the state where we are at destination \(i\) with visited set mask to an unvisited destination \(j\) $\( dp[\text{mask} \mid 2^j][j] \leftarrow dp[\text{mask}][i] + \text{distC}[i][C_j] \)$

Answer: The minimum value to go to \(N\) from the last visited destination \(i\), after visiting all destinations (where full is the set with all bits set) $\( \text{ans} = \min_{i} \left( dp[\text{full}][i] + \text{distC}[i][N] \right) \)$

Complexity

We run Dijkstra’s algorithm \(K+1\) times and then perform the Bit DP transitions.

• Time Complexity: \(O\big((K+1)\,(M \log N) + 2^K \cdot K^2\big)\)
  • Dijkstra phase: \((K+1) \times O(M \log N)\)
  • Bit DP phase: \(O(2^K \cdot K^2)\) (which is \(2^{15} \cdot 15^2 \approx 7.4 \times 10^6\), fast enough)
• Space Complexity: \(O\big((K+1)\,N + 2^K \cdot K\big)\)
  • Distance arrays for each Dijkstra run and the DP table

Implementation Details

• Beware of overflow: Since the maximum edge weight \(W_i\) is \(10^9\) and a path can contain multiple edges, the total distance must be stored in a 64-bit integer (long long). To prevent overflow when adding distances, it is safe to set INF to a value like LLONG_MAX/4.

• Implement Dijkstra using an adjacency list and a priority queue. Do not forget the pruning step: skip the state if d > dist[u], as it represents outdated information.

• Be careful not to confuse the destination index \(i\) (\(0\) to \(K-1\)) with the vertex ID \(C_i\) when referencing the DP table. Since distC[i] is the “distance array from the \(i\)-th destination”, the distance to another destination \(C_j\) must be accessed using its vertex ID, like distC[i][C[j]].

• By iterating mask in ascending order, the source states of transitions are guaranteed to be computed beforehand, allowing the DP to proceed correctly.

  Source Code

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

int main(){
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    vector<vector<pair<int,long long>>> g(N+1);
    for(int i=0;i<M;i++){
        int u,v; long long w;
        scanf("%d %d %lld", &u, &v, &w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    vector<int> C(K);
    for(int i=0;i<K;i++) scanf("%d", &C[i]);
    
    const long long INF = LLONG_MAX/4;
    
    auto dijkstra = [&](int s)->vector<long long>{
        vector<long long> dist(N+1, INF);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        dist[s]=0;
        pq.push({0,s});
        while(!pq.empty()){
            auto [d,u]=pq.top(); pq.pop();
            if(d>dist[u]) continue;
            for(auto [v,w]:g[u]){
                if(dist[v]>d+w){
                    dist[v]=d+w;
                    pq.push({dist[v],v});
                }
            }
        }
        return dist;
    };
    
    // Dijkstra from node 1
    vector<long long> distFrom1 = dijkstra(1);
    
    // Dijkstra from each delivery point
    vector<vector<long long>> distC(K);
    for(int i=0;i<K;i++) distC[i] = dijkstra(C[i]);
    
    // dist between deliveries
    // dp
    int full = (1<<K)-1;
    vector<vector<long long>> dp(1<<K, vector<long long>(K, INF));
    for(int i=0;i<K;i++){
        dp[1<<i][i] = distFrom1[C[i]];
    }
    for(int mask=0; mask<=full; mask++){
        for(int i=0;i<K;i++){
            if(!(mask&(1<<i))) continue;
            if(dp[mask][i]==INF) continue;
            for(int j=0;j<K;j++){
                if(mask&(1<<j)) continue;
                long long nd = dp[mask][i] + distC[i][C[j]];
                int nmask = mask|(1<<j);
                if(dp[nmask][j] > nd) dp[nmask][j] = nd;
            }
        }
    }
    
    long long ans = INF;
    for(int i=0;i<K;i++){
        if(dp[full][i]==INF) continue;
        ans = min(ans, dp[full][i] + distC[i][N]);
    }
    
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.