Official

E - 配達員の巡回 / Delivery Person's Round Editorial by admin

gpt-5.3-codex

Overview

This problem asks us to find “the shortest time to start from location \(1\), visit all \(K\) specified delivery destinations, and return to \(1\).”
The essence is to first compute shortest distances between important locations, then solve using bit DP (Traveling Salesman-type DP) leveraging \(K \le 15\).

Analysis

The tricky part of this problem is that while the total number of vertices \(N, M\) in the graph can be as large as \(5\times 10^4\), the number of delivery destinations that must be visited is only \(K\le 15\), which is small.

If we naively “search on the graph while maintaining state (current position and which destinations have been visited),” the number of states becomes \(N \times 2^K\), which is too large.
At maximum, this would be \(5\times 10^4 \times 2^{15}\), which is not practical.

The key observation is as follows:

  • What we actually need to optimize over is only “location \(1\) and the \(K\) destinations” (a total of \(K+1\) locations)
  • The travel cost between them can be replaced by the shortest distances on the original graph
    (Concatenating shortest paths does not incur any loss due to the triangle inequality)

In other words, instead of running DP directly on the original graph, we use a two-phase approach:

  1. Build a shortest distance matrix between important locations (\(1\) and the \(V_i\)’s)
  2. Solve “minimum cost to visit all destinations and return” on this complete graph using bit DP

This allows us to solve the problem efficiently.

Algorithm

  1. Define the important locations array as important = [1] + V (length \(L=K+1\)).
  2. Run Dijkstra from each important location as the source, and record the shortest distance to every other important location in pair[i][j].
    • This completes the “distance table between important locations.”
  3. Perform bit DP.
    • dp[mask][i]
      = “the minimum cost when starting from location \(1\), having visited the set of destinations represented by mask, and currently being at destination i (0-based)”
  4. Initialization:
    • dp[1<<i][i] = pair[0][i+1]
      (going directly from \(1\) to each destination)
  5. Transition:
    • From dp[mask][i], move to an unvisited destination j
      dp[mask | (1<<j)][j] = min(..., dp[mask][i] + pair[i+1][j+1])
  6. After full visitation full=(1<<K)-1, add the cost of returning from each endpoint i to location \(1\) and take the minimum.
    • ans = min(dp[full][i] + pair[i+1][0])

This matches the processing in the code.

Complexity

  • Time complexity:
    Running Dijkstra \(K+1\) times gives
    \(O((K+1)\, M \log N)\)
    • bit DP is \(O(2^K K^2)\)
      So the overall complexity is
      \(O((K+1)M\log N + 2^K K^2)\)
  • Space complexity:
    Graph \(O(N+M)\), distance table \(O((K+1)^2)\), DP table \(O(2^K K)\)
    Total: \(O(N+M+2^K K)\)

Implementation Notes

  • Since edge weights are positive, Dijkstra works fine for shortest paths.

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

  • The if d != dist[v]: continue inside dijkstra is a standard optimization to discard stale heap entries.

  • Pay attention to index correspondence:

    • pair[0] corresponds to location \(1\)
    • pair[i+1] corresponds to destination V[i]
  • Don’t forget to add the “return cost (endpoint → 1)” at the end.

    Source Code

import sys
import heapq

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

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    V = list(map(int, input().split()))
    
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    important = [1] + V  # index 0 is node 1, indices 1..K are destinations
    L = K + 1
    
    # Pairwise shortest paths among important nodes
    pair = [[0] * L for _ in range(L)]
    for i in range(L):
        dist = dijkstra(important[i], graph, N)
        for j in range(L):
            pair[i][j] = dist[important[j]]
    
    INF = 10**30
    # dp[mask][i]: minimum cost to start from node 1, visit destinations in mask,
    # and end at destination i (0-based for V list)
    size = 1 << K
    dp = [[INF] * K for _ in range(size)]
    
    for i in range(K):
        dp[1 << i][i] = pair[0][i + 1]
    
    for mask in range(size):
        row = dp[mask]
        for i in range(K):
            cur = row[i]
            if cur >= INF:
                continue
            for j in range(K):
                if (mask >> j) & 1:
                    continue
                nmask = mask | (1 << j)
                nd = cur + pair[i + 1][j + 1]
                if nd < dp[nmask][j]:
                    dp[nmask][j] = nd
    
    full = (1 << K) - 1
    ans = INF
    for i in range(K):
        val = dp[full][i] + pair[i + 1][0]
        if val < ans:
            ans = val
    
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.