Overview

Starting from office \(S\), we need to find the minimum travel time to visit all \(K(\le 15)\) delivery destinations and return to \(S\). We solve this “graph traversal (TSP)” problem by exploiting the fact that the number of delivery destinations is small.

Analysis

Key Observation

• The road network is large with \(N\le 10^4, M\le 2\times 10^4\), but the number of locations we must visit is only \(K+1\le 16\) in total (office \(S\) plus \(K\) delivery destinations) — this is the crucial point.
• Since the delivery order is free, what we essentially want to do is: Build a complete graph with only \(S\) and the delivery destinations as vertices, then find the shortest tour on it.

Why a Naive Approach Fails

• Enumerating all delivery orderings gives \(K!\) permutations. For \(K=15\), \(15!\approx 1.3\times 10^{12}\), which is infeasible (TLE).
• Moreover, if we compute the shortest path on the original large graph for each pair every time we fix an ordering, it becomes even heavier.

Solution Strategy

1. First, collect only the shortest distances between the required locations (\(S\) and delivery destinations) → Run Dijkstra’s algorithm from each such location to build a distance table.
2. Using that distance table, solve the tour problem over the \(K\) delivery destinations with bitDP (the classic DP for the Traveling Salesman Problem).

Example: If there are 3 delivery destinations (A, B, C), instead of directly enumerating all orderings like “S→A→C→B→S”, we update minimum values using the state of “which destinations have been visited so far (as a set)” and “which delivery destination we are currently at.”

Algorithm

1. Building the Distance Table (Dijkstra)

• Prepare the target locations terminals = [S] + D (size \(t=K+1\)).
• Run Dijkstra’s algorithm from each terminals[i] to obtain shortest distances dist on the original graph.
• Fill in the distance table dist_mat[i][j] = dist[terminals[j]]. This extracts only the travel costs between the required locations.

2. Shortest Tour via bitDP (TSP)

• Number the delivery destinations as \(1..K\) and the office as \(0\) (terminals[0]=S).
• State:
  • mask: a bitmask representing which delivery destinations have been visited (size \(2^K\))
  • last: the last delivery destination visited (\(1..K\))
• DP definition:
  • \(dp[mask][last] =\) “the minimum time to have visited all delivery destinations in set mask, ending at last”
• Initialization:
  • Going to just one destination first: \(dp[1<<(i-1)][i] = dist\_mat[0][i]\)
• Transition:
  • Choose the next delivery destination nxt to visit: \(dp[mask\cup\{nxt\}][nxt] = \min(dp[mask\cup\{nxt\}][nxt],\ dp[mask][last] + dist\_mat[last][nxt])\)
• Answer:
  • From the fully visited state full = (1<<K)-1, return to the office: \(\min_{last} \left(dp[full][last] + dist\_mat[last][0]\right)\)

Complexity

• Time complexity:
  • Dijkstra run \(K+1\) times: \(O((K+1)\, M \log N)\)
  • bitDP: \(O(2^K \cdot K^2)\) Overall: \(O((K+1)\, M \log N + 2^K K^2)\)
• Space complexity:
  • Graph: \(O(N+M)\)
  • Distance arrays (for Dijkstra): \(O(N)\) (though in the code, dist is stored for each starting point, totaling \(O((K+1)N)\))
  • DP: \(O(2^K \cdot K)\) Overall roughly \(O(N+M + (K+1)N + 2^K K)\)

Implementation Notes

• Since the number of vertices is large, always use Dijkstra’s algorithm (with a priority queue) for shortest distances (edge weights are positive).

• Designing the bitDP so that mask manages “only delivery destinations” without including office \(S\) keeps the implementation concise.

• Distances can become very large, so use a sufficiently large value like INF = 10**30.

• Since the input is large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys
import heapq

def dijkstra(start, g, n):
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[start] = 0
    hq = [(0, start)]
    push = heapq.heappush
    pop = heapq.heappop
    while hq:
        d, v = pop(hq)
        if d != dist[v]:
            continue
        for to, w in g[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                push(hq, (nd, to))
    return dist

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it); v = next(it); w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))

    S = next(it)
    K = next(it)
    D = [next(it) for _ in range(K)]

    terminals = [S] + D  # index 0 is S, 1..K are deliveries
    t = K + 1

    dist_mat = [[0] * t for _ in range(t)]
    all_dists = []
    for s in terminals:
        all_dists.append(dijkstra(s, g, N))
    for i in range(t):
        di = all_dists[i]
        for j in range(t):
            dist_mat[i][j] = di[terminals[j]]

    INF = 10**30
    size = 1 << K
    dp = [[INF] * (K + 1) for _ in range(size)]
    for i in range(1, K + 1):
        dp[1 << (i - 1)][i] = dist_mat[0][i]

    for mask in range(size):
        row = dp[mask]
        for last in range(1, K + 1):
            cur = row[last]
            if cur >= INF:
                continue
            for nxt in range(1, K + 1):
                bit = 1 << (nxt - 1)
                if mask & bit:
                    continue
                nm = mask | bit
                val = cur + dist_mat[last][nxt]
                if val < dp[nm][nxt]:
                    dp[nm][nxt] = val

    full = size - 1
    ans = INF
    for last in range(1, K + 1):
        val = dp[full][last] + dist_mat[last][0]
        if val < ans:
            ans = val

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.