Overview

This problem is a variant of the Traveling Salesman Problem (TSP), where we must depart from the office, visit all delivery destinations, and return to the office via the shortest route. However, since the graph is large, we need to precompute the shortest distances between all relevant nodes and then solve the TSP considering only the delivery destinations.

Analysis

• The graph can be as large as \(N=10000\) nodes and \(M=20000\) edges, so we cannot directly compute shortest distances between all pairs of nodes.
• However, the number of delivery destinations \(K\) is at most 15, which is small, so we can consider a subgraph consisting of only the office \(S\) and the delivery destinations \(D_j\).
• First, we run Dijkstra’s algorithm from the office \(S\) and each delivery destination \(D_j\) as the source to precompute the shortest distances between these points.
• Then, on the complete graph with only the office and delivery destinations as vertices, we solve the Traveling Salesman Problem (TSP) using dynamic programming (bit DP).

Algorithm

1. Precomputation: Run Dijkstra’s algorithm from the office \(S\) and all delivery destinations \(D_j\) as sources to compute the shortest distances from each of these points to all intersections. This gives us the shortest distances \(dists[u][v]\) between \(S\) and \(D_j\).
2. TSP Setup: Define the vertex set as \(\{S, D_1, D_2, \ldots, D_K\}\), with edge weights set to the precomputed shortest distances. On this complete graph, find the shortest route that starts from \(S\), visits all vertices, and returns to \(S\).
3. Bit DP:
   • \(dp[mask][i]\): The minimum cost when the set of visited vertices is \(mask\) (bitmask) and the last visited vertex is the \(i\)-th one.
   • Initial state: \(dp[1][0] = 0\) (the office \(S\) is visited first).
   • Transition: For each unvisited vertex \(j\), \(dp[new\_mask][j] = \min(dp[new\_mask][j], dp[mask][i] + dists[i][j])\).
4. Computing the Answer: From the state where all vertices have been visited (\(mask = (1<<(K+1))-1\)), add the cost \(dists[i][S]\) of returning from the last vertex \(i\) to the office \(S\), and take the minimum value.

Complexity

• Time complexity: \(O((K+1) \cdot (M \log N) + O(2^{K+1} \cdot (K+1)^2)\)
  • Running Dijkstra’s algorithm \(K+1\) times: \(O((K+1) \cdot (M \log N))\)
  • Bit DP: \(O(2^{K+1} \cdot (K+1)^2)\)
• Space complexity: \(O(N + M + 2^{K+1} \cdot (K+1))\)
  • Graph representation: \(O(N + M)\)
  • Precomputed distance table: \(O((K+1) \cdot N)\)
  • DP table: \(O(2^{K+1} \cdot (K+1))\)

Implementation Notes

• In Dijkstra’s algorithm, compute the shortest distances from each source and store them in the array dists.

• In the point list points, store the office \(S\) at index 0 and the delivery destinations from index 1 onward.

• In the bit DP, manage states using bitmasks and process transitions to unvisited vertices in a loop.

• Initialize with a large value (\(10^{18}\)) to prevent overflow.

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    S = int(next(it)); K = int(next(it))
    Ds = [int(next(it)) for _ in range(K)]
    
    points = [S] + Ds
    dists = {}
    
    for start in points:
        dist = [10**18] * (n+1)
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            d, u = heapq.heappop(heap)
            if d != dist[u]:
                continue
            for v, w in graph[u]:
                if dist[v] > d + w:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
        dists[start] = dist
    
    size = K + 1
    dp = [[10**18] * size for _ in range(1 << size)]
    dp[1][0] = 0
    
    for mask in range(1 << size):
        for i in range(size):
            if dp[mask][i] == 10**18:
                continue
            for j in range(size):
                if mask & (1 << j):
                    continue
                new_mask = mask | (1 << j)
                u = points[i]
                v = points[j]
                cost = dists[u][v]
                if dp[new_mask][j] > dp[mask][i] + cost:
                    dp[new_mask][j] = dp[mask][i] + cost
    
    ans = 10**18
    full_mask = (1 << size) - 1
    for i in range(1, size):
        u = points[i]
        cost_back = dists[u][S]
        if dp[full_mask][i] + cost_back < ans:
            ans = dp[full_mask][i] + cost_back
            
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.