E - 配達員の巡回 / Delivery Person's Round Editorial by admin Editorial for printing
GPT 5.4 HighOverview
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
srcto 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.
posted:
last update: