E - 配達員の巡回 / Delivery Person's Round 解説 by admin
Claude 4.6 Opus (Thinking)Overview
This problem asks us to find the shortest route that starts from point \(1\), visits all \(K\) delivery destinations, and returns to point \(1\). Given the constraint \(K \leq 15\), we solve the Traveling Salesman Problem (TSP) using bitmask DP.
Analysis
Naive Approach and Its Issues
There are \(K!\) possible orderings to visit the \(K\) delivery destinations. When \(K = 15\), \(15! \approx 1.3 \times 10^{12}\), so full enumeration is far too slow.
Key Observations
Intermediate points can be ignored: We only need to focus on point \(1\) and the \(K\) delivery destinations — a total of \(K+1\) “key points.” Movement between key points can be done via shortest paths on the original graph, and we don’t need to worry about the intermediate routes.
Precomputation of the distance matrix: By running Dijkstra’s algorithm from each key point, we can compute all pairwise shortest distances between key points. This reduces the problem to “TSP on a complete graph with \((K+1)\) vertices.”
Bitmask DP: Since \(K \leq 15\), we can represent “which delivery destinations have been visited” as a \(K\)-bit integer and use DP to find the optimal visiting order. The number of states is \(2^K \times (K+1)\), which is approximately \(500{,}000\) when \(K=15\).
Algorithm
Step 1: Precomputation of Shortest Distances
The key points are point \(1\) and the delivery destinations \(V_1, \ldots, V_K\), totaling \(K+1\) points. We run Dijkstra’s algorithm from each of these points to compute shortest distances to all vertices. This gives us the distance matrix \(\text{key\_dist}[i][j]\) between key points.
Step 2: TSP via Bitmask DP
- State: \(dp[\text{mask}][u]\) = the minimum cost when the set of visited delivery destinations is \(\text{mask}\) and we are currently at key point \(u\)
- Initial state: \(dp[0][0] = 0\) (we are at point \(1\) and have not visited any delivery destination yet)
- Transition: From state \((\text{mask}, u)\), move to an unvisited delivery destination \(j\):
\[dp[\text{mask} \mid (1 \ll j)][j+1] = \min\left(dp[\text{mask} \mid (1 \ll j)][j+1],\; dp[\text{mask}][u] + \text{key\_dist}[u][j+1]\right)\]
- Answer: From the state where all delivery destinations have been visited, \(\text{full\_mask} = 2^K - 1\), add the cost of returning to point \(1\):
\[\text{ans} = \min_{u} \left( dp[\text{full\_mask}][u] + \text{key\_dist}[u][0] \right)\]
Complexity
- Time complexity: \(O((K+1) \cdot (N + M) \log N + 2^K \cdot K^2)\)
- Running Dijkstra \(K+1\) times: \(O((K+1) \cdot (N + M) \log N)\)
- Bitmask DP: \(O(2^K \cdot K^2)\) (up to \(K\) transitions from each state)
- Fast enough for \(K = 15, N = M = 5 \times 10^4\)
- Space complexity: \(O((K+1) \cdot N + 2^K \cdot K)\)
- Dijkstra distance arrays: \(O((K+1) \cdot N)\)
- DP table: \(O(2^K \cdot (K+1))\)
Implementation Notes
Index management for key points: By assigning index \(0\) to point \(1\) and index \(i\) (\(1 \leq i \leq K\)) to delivery destination \(V_i\), bit \(j\) of the bitmask corresponds to delivery destination \(V_{j+1}\) (key node index \(j+1\)), which helps avoid confusion.
Fast input: In Python, reading all input at once with
sys.stdin.buffer.read()can improve speed when handling large inputs.Handling infinity: Initialize unreachable states with
float('inf')and skip them during transitions to avoid unnecessary computations.Source Code
import heapq
import sys
def dijkstra(graph, start, N):
dist = [float('inf')] * (N + 1)
dist[start] = 0
hq = [(0, start)]
while hq:
d, u = heapq.heappop(hq)
if d > dist[u]:
continue
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(hq, (nd, v))
return dist
def main():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1
K = int(input_data[idx]); idx += 1
V = []
for i in range(K):
V.append(int(input_data[idx])); idx += 1
graph = [[] for _ in range(N + 1)]
for i in range(M):
a = int(input_data[idx]); idx += 1
b = int(input_data[idx]); idx += 1
c = int(input_data[idx]); idx += 1
graph[a].append((b, c))
graph[b].append((a, c))
# Key nodes: node 1 (index 0) and V[0..K-1] (indices 1..K)
key_nodes = [1] + V # length K+1
# Compute shortest paths from each key node
# dist_from[i] = shortest distance array from key_nodes[i]
dist_from = []
for node in key_nodes:
dist_from.append(dijkstra(graph, node, N))
# Build distance matrix between key nodes
# key_dist[i][j] = shortest distance from key_nodes[i] to key_nodes[j]
num_keys = K + 1
key_dist = [[0] * num_keys for _ in range(num_keys)]
for i in range(num_keys):
for j in range(num_keys):
key_dist[i][j] = dist_from[i][key_nodes[j]]
# TSP with bitmask DP
# State: (visited subset of delivery nodes (bits 0..K-1 for V[0]..V[K-1]), current key node index)
# We need to visit all K delivery nodes and return to node 0 (which is key_nodes[0] = 1)
full_mask = (1 << K) - 1
INF = float('inf')
# dp[mask][i] = min cost to have visited the delivery nodes in mask, currently at key node i
# i ranges from 0 to K (0 = node 1, 1..K = delivery nodes)
dp = [[INF] * num_keys for _ in range(1 << K)]
# Start at key node 0 (node 1), no deliveries done
dp[0][0] = 0
for mask in range(1 << K):
for u in range(num_keys):
if dp[mask][u] == INF:
continue
cur_cost = dp[mask][u]
# Try going to each delivery node
for j in range(K):
if mask & (1 << j):
continue
v = j + 1 # key node index for V[j]
new_mask = mask | (1 << j)
new_cost = cur_cost + key_dist[u][v]
if new_cost < dp[new_mask][v]:
dp[new_mask][v] = new_cost
# Find minimum cost: visit all deliveries then return to node 1
ans = INF
for u in range(num_keys):
if dp[full_mask][u] == INF:
continue
total = dp[full_mask][u] + key_dist[u][0]
if total < ans:
ans = total
print(ans)
if __name__ == '__main__':
main()
This editorial was generated by claude4.6opus-thinking.