Official

E - 配送計画 / Delivery Plan Editorial by admin

or-glm5.2-high

Overview

This problem asks us to find the minimum travel time to start from vertex 1, visit all \(K\) specified locations at least once, and then arrive at vertex \(N\).

Analysis

To solve this problem, a naive approach would be to “try all possible visiting orders”. The total number of ways to visit the \(K\) locations is \(K!\). Since \(K\) can be up to 15, \(15! \approx 1.3 \times 10^{12}\), which is too large to compute within the time limit.

However, focusing on the fact that \(K\) is at most 15, we can use bit DP (Dynamic Programming with bitmask) to manage the visited states and search for the optimal order in \(O(K^2 2^K)\) time.

To perform bit DP, we need the travel times between the target locations. On the original graph, traveling directly from location A to location B might not be the fastest; it could be faster to go via other vertices. Therefore, we need to precalculate the shortest paths between all important locations.

In this problem, the “important locations” are the starting vertex (vertex 1), the \(K\) destinations, and the ending vertex (vertex \(N\)), making a total of \(K+2\) locations.

By running Dijkstra’s algorithm starting from each of these \(K+2\) locations, we can find the shortest travel time between any pair of important locations. After that, we can efficiently calculate the minimum travel time by performing bit DP on the complete graph consisting of these \(K+2\) locations.

Algorithm

  1. List Important Locations: Store the starting vertex (1), the \(K\) destinations (\(C_1, \dots, C_K\)), and the ending vertex (\(N\)) in a list. Let the indices of this list be \(0\) to \(K+1\).
  2. Calculate Shortest Paths: Run Dijkstra’s algorithm starting from each important location to find the shortest distances to all other vertices. Use this to construct a shortest distance matrix dist_matrix between the important locations.
  3. Path Search via bit DP:
    • Define the state dp[i][S] as “the minimum travel time from the starting vertex when the set of already visited destinations is \(S\) (represented as a bitmask) and the last visited destination is \(i\) (0-indexed)”.
    • As the initial state, assign the direct distance from the starting vertex to each destination \(i\), which is dist_matrix[0][i+1], to dp[i][1 << i].
    • From each state dp[i][S], transition to a yet unvisited destination \(j\), updating the value of dp[j][S | (1 << j)].
  4. Compute the Answer: For each destination \(i\), add the travel time from \(i\) to the ending vertex (\(N\)) to the fully visited state (\(S = 2^K - 1\)), and output the minimum value among them as the answer.

Complexity

  • Time Complexity: \(O((K+2)M \log N + K^2 2^K)\)
    • Running Dijkstra’s algorithm \(K+2\) times takes \(O((K+2) M \log N)\) time.
    • The transitions of the bit DP take \(O(K^2 2^K)\) time.
    • This is well within the time limit under the given constraints.
  • Space Complexity: \(O(N + K^2)\)
    • The adjacency list of the graph takes \(O(N+M)\) space, and the distance matrix and DP table take \(O(K^2)\) space.

Key Implementation Points

  • Since the travel time of each road \(W_i\) can be up to \(10^9\), the accumulated travel time can exceed the range of a 32-bit signed integer (approx. \(2 \times 10^9\)). Therefore, use long long (or 64-bit integer) to store distances.

  • For the infinity value (INF), choose a sufficiently large value like 1e18, considering that the maximum possible distance can be around \(10^5 \times 10^9 = 10^{14}\).

  • In the DP array for bit DP, the destinations are indexed from $0 \sim K-1$. However, in dist_matrix, the starting vertex is at index \(0\), the destinations are at indices $1 \sim K$, and the ending vertex is at index \(K+1\). Be careful with index offsets (such as i+1) during implementation.

    Source Code

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

This editorial was generated by or-glm5.2-high.