公式

E - 配達員の巡回 / Delivery Person's Round 解説 by admin

GPT 5.4 High

Overview

Focus only on point \(1\) and the \(K\) delivery destinations, and compute the shortest distances between them first. Then the problem reduces to finding the “shortest tour starting from point \(1\), visiting all delivery destinations at least once, and returning to \(1\),” which can be solved using bit DP leveraging \(K \le 15\).

Observations

In this problem, you are allowed to pass through the same point or the same road any number of times during the actual route. At first glance, this seems quite complex because you need to consider:

  • In what order to visit the delivery destinations
  • Which roads to take along the way
  • Which route to take when returning

Key Insight 1: Once the order is fixed, each segment should use the shortest path

For example, suppose the order of visiting delivery destinations is fixed as:

\(1 \to V_3 \to V_1 \to V_2 \to 1\)

In this case, for the segment from \(1\) to \(V_3\), the segment from \(V_3\) to \(V_1\), etc., it is optimal to use the shortest path for each.

That is, the minimum cost for visiting in this order is:

\( \mathrm{dist}(1, V_3) + \mathrm{dist}(V_3, V_1) + \mathrm{dist}(V_1, V_2) + \mathrm{dist}(V_2, 1) \)

where \(\mathrm{dist}(u,v)\) is the shortest distance on the original graph.

Therefore, instead of directly dealing with the entire large graph, it suffices to know only the shortest distances between the special points:

  • Special points: \(1, V_1, V_2, \dots, V_K\)

Key Insight 2: All we need is the “shortest distances between special points”

Since the number of points \(N\) can be up to \(5 \times 10^4\), computing all-pairs shortest paths (e.g., Floyd-Warshall) is infeasible. However, we only need distances between at most \(K+1 \le 16\) special points.

Since edge weights are positive, it suffices to run Dijkstra’s algorithm once from each special point. This gives us:

  • Shortest distances from \(1\) to each delivery destination
  • Shortest distances between each pair of delivery destinations

Key Insight 3: The visiting order of destinations can be managed with bit DP

At this point, the problem can be rephrased as follows:

  • Start from point \(1\)
  • Visit all \(K\) delivery destinations
  • Return to \(1\) at the end
  • Movement cost is the shortest distance between special points

This is a classic “tour ordering” problem, and can be solved with bit DP using \(K \le 15\).


Why naive approaches fail

1. Brute-force over all permutations of destinations

Enumerating all orderings of destinations gives \(K!\) possibilities. For \(K=15\):

\( 15! \approx 1.3 \times 10^{12} \)

which is far too many to handle.

2. Computing all-pairs shortest paths

Since \(N\) can be up to \(5 \times 10^4\), \(O(N^3)\) is completely infeasible.


How to solve it

  • Run Dijkstra only from the special points \(1, V_1, \dots, V_K\) to compute only the necessary shortest distances
  • Then use a DP with the destination set represented as bits to find the minimum tour cost

These two steps fit within the constraints.

Algorithm

1. Build the graph

Since roads are bidirectional, add edges to the adjacency list in both directions.


2. Compute shortest distances between special points using Dijkstra

Define the special points as:

\( \text{special} = [1, V_1, V_2, \dots, V_K] \)

Run Dijkstra from each special point and extract only the shortest distances to other special points. This produces a distance table pair between \(S = K+1\) points.

In the code, dijkstra(src):

  • Computes shortest distances from src to all vertices
  • Records only the distances to vertices belonging to special in res

Also, since we only need distances to special points, the search is terminated early once the shortest distances to all special points have been determined, providing a slight speedup.


3. Perform bit DP

Define the following DP:

\( dp[\text{mask}][i] \)

= “The minimum cost when starting from point \(1\), having visited the set of destinations represented by mask, and currently being at \(V_i\)”

Here mask is a \(K\)-bit integer, where the \(j\)-th bit being 1 means \(V_j\) has been visited.

Initial values

When visiting only one destination \(V_i\) first:

\( dp[1 \ll i][i] = \mathrm{dist}(1, V_i) \)

Transitions

If currently at \(V_i\) and going next to an unvisited \(V_j\):

$

dp[\text{mask} \cup {j}][j]

\min\left( dp[\text{mask}][i] + \mathrm{dist}(V_i, V_j) \right) $

Final answer

After visiting all destinations, return from the last destination \(V_i\) to \(1\):

\( \min_i \left( dp[(1 \ll K)-1][i] + \mathrm{dist}(V_i, 1) \right) \)

is the answer.


Why this is correct

Consider any optimal route and extract only the order in which each destination is visited for the first time. This order takes the form:

\( 1 \to V_{p_1} \to V_{p_2} \to \cdots \to V_{p_K} \to 1 \)

The movement between consecutive points in the original route can pass through anything, but replacing each segment with the shortest path does not increase the cost. Therefore, the optimal solution can be found by considering the “tour problem on a complete graph with shortest distances between special points as edge weights.”

Since the bit DP minimizes over all visited subsets and last visited points for this tour problem, it correctly finds the answer.

Complexity

  • Time complexity: \(O((K+1)\, M \log N + K^2 2^K)\)
  • Space complexity: \(O(N + M + K 2^K)\)

Details

  • Dijkstra is run \(K+1\) times, giving \(O((K+1) M \log N)\)
  • The DP has \(2^K \times K\) states, each transitioning to at most \(K\) others, giving \(O(K^2 2^K)\)

Since \(K \le 15\), the bit DP runs comfortably within time limits.

Implementation Notes

  • Edge weights and the answer can be large, so use a sufficiently large value like INF = 10**30
  • Since the graph is weighted, use Dijkstra with a priority queue rather than BFS
  • Since we only need distances between special points, extract only the distances to special points from the Dijkstra results instead of storing everything
  • In the bit DP, unvisited destinations are efficiently enumerated using bit operations

In particular, this code uses rem & -rem to extract the lowest set bit, efficiently iterating over unvisited destinations.

Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    K = next(it)

    V = [next(it) for _ in range(K)]

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = next(it)
        b = next(it)
        c = next(it)
        g[a].append((b, c))
        g[b].append((a, c))

    special = [1] + V
    S = K + 1
    INF = 10**30

    sp_idx = [-1] * (N + 1)
    for i, v in enumerate(special):
        sp_idx[v] = i

    heappush = heapq.heappush
    heappop = heapq.heappop

    def dijkstra(src):
        dist = [INF] * (N + 1)
        dist[src] = 0
        res = [INF] * S
        found = 0
        pq = [(0, src)]

        while pq and found < S:
            d, v = heappop(pq)
            if d != dist[v]:
                continue

            idx = sp_idx[v]
            if idx != -1 and res[idx] == INF:
                res[idx] = d
                found += 1

            for to, w in g[v]:
                nd = d + w
                if nd < dist[to]:
                    dist[to] = nd
                    heappush(pq, (nd, to))

        return res

    pair = [dijkstra(s) for s in special]

    d0 = pair[0][1:]
    dt = [pair[i + 1][1:] for i in range(K)]

    allmask = (1 << K) - 1
    dp = [[INF] * K for _ in range(1 << K)]

    for i in range(K):
        dp[1 << i][i] = d0[i]

    bit_to_idx = [0] * (1 << K)
    for i in range(K):
        bit_to_idx[1 << i] = i

    for mask in range(1 << K):
        rem_base = allmask ^ mask
        if rem_base == 0:
            continue
        row = dp[mask]
        for i in range(K):
            cur = row[i]
            if cur == INF:
                continue
            di = dt[i]
            rem = rem_base
            while rem:
                lsb = rem & -rem
                j = bit_to_idx[lsb]
                nd = cur + di[j]
                nrow = dp[mask | lsb]
                if nd < nrow[j]:
                    nrow[j] = nd
                rem ^= lsb

    ans = INF
    final_row = dp[allmask]
    for i in range(K):
        cand = final_row[i] + d0[i]
        if cand < ans:
            ans = cand

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.4-high.