Overview

This problem asks us to find the minimum cost of a route that visits multiple specified vertices on a graph in the shortest time and returns to the starting point at the end. It is a variant of the so-called “Traveling Salesman Problem (TSP).”

Analysis

First, this problem cannot be solved by simple brute-force search. This is because the number of delivery destinations \(K\) is at most \(15\), the number of combinations for visiting order is \(K!\), and on top of that, we need to find the shortest path for each movement, resulting in extremely high computational cost.

However, there are notable constraints: - The number of vertices \(N\) in the graph is at most \(10\,000\), and the number of edges \(M\) is at most \(20\,000\). - But what we actually need to consider is only the \(K+1\) points: the office and the delivery destinations.

Therefore, we can solve this efficiently with the following steps: 1. Precompute the shortest distances between the office \(S\) and all delivery destinations \(D_1, ..., D_K\) (all-pairs shortest distances among these points). 2. Using the distance information of only these \(K+1\) points, optimize the visiting order. The classic bit DP approach for TSP can be applied here.

By handling only the shortest distances between the necessary vertices rather than the entire graph, we can significantly reduce the computational cost.

Algorithm

The solution is divided into the following steps:

1. Precomputation of Shortest Distances (Dijkstra’s Algorithm)

• Run Dijkstra’s algorithm from each of the \(K+1\) points, including the office \(S\) and each delivery destination \(D_j\), as the source.
• This allows us to precompute the shortest travel time between any pair of these points.

2. Solving the Traveling Salesman Problem (TSP) (Bit DP)

• \(dp[mask][i]\): The minimum cost when the set of visited delivery destinations is \(mask\) and the last visited location is \(i\) (0 represents the office, 1 through K represent delivery destinations).
• Initial state: \(dp[0][0] = 0\)
• Transition: For each unvisited delivery destination \(j\): $\( dp[mask \cup \{j\}][j] = \min(dp[mask \cup \{j\}][j],\ dp[mask][i] + \text{cost}(i \to j)) \)$
• Finally, add the cost of returning from the last visited vertex to the office and update the answer.

In this way, we find the minimum cost of visiting all delivery destinations and returning to the starting point.

Complexity

• Number of Dijkstra executions: \(K+1\) times
• Complexity of one Dijkstra execution: \(O(M \log N)\)
• Number of states in bit DP: \(O(2^K \cdot K)\)
• Transitions in bit DP: Since there are \(K\) transitions from each state, \(O(2^K \cdot K^2)\)

Therefore,

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

Implementation Notes

• Dijkstra’s algorithm is implemented with an adjacency list and sped up using a priority queue.

• In the bit DP, the visited state is represented as a bitmask and managed together with the index of the last visited location.

• Since delivery destination indices are handled as 1-origin, be careful with array access (e.g., dp[mask][j+1]).

• Don’t forget to include the process of returning to the office at the end.

  Source Code

import heapq
from itertools import permutations
import sys

def dijkstra(graph, start, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    S = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    D = list(map(int, data[idx:idx+K])); idx += K
    
    # 配達先＋営業所のノードリスト
    nodes = [S] + D
    node_index = {node: i for i, node in enumerate(nodes)}
    
    # 全点対最短距離を計算
    dist_all = {}
    for node in nodes:
        dist_all[node] = dijkstra(graph, node, N)
    
    # 配達先間および営業所との距離行列
    # dp[bit][i] := 訪問済み集合bit, 最後に訪れた場所がiのときの最小コスト
    INF = float('inf')
    dp = [[INF] * (K + 1) for _ in range(1 << K)]
    dp[0][0] = 0  # 初期位置は営業所(S)

    # ビットDP
    for mask in range(1 << K):
        for i in range(K + 1):
            if dp[mask][i] == INF:
                continue
            current_node = nodes[i]
            for j in range(K):
                if not (mask & (1 << j)):
                    next_mask = mask | (1 << j)
                    next_node = D[j]
                    cost = dist_all[current_node][next_node]
                    if dp[next_mask][j + 1] > dp[mask][i] + cost:
                        dp[next_mask][j + 1] = dp[mask][i] + cost

    # 全ての配達先を訪れた後、営業所に戻る
    ans = INF
    full_mask = (1 << K) - 1
    for i in range(K + 1):
        if dp[full_mask][i] != INF:
            last_node = nodes[i]
            return_cost = dist_all[last_node][S]
            ans = min(ans, dp[full_mask][i] + return_cost)
    
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.