公式

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

  1. 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.

  2. 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.”

  3. 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.