E - 配達員の巡回 / Delivery Person's Round 解説 by admin 印刷ページ
gpt-5.3-codexOverview
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:
- Build a shortest distance matrix between important locations (\(1\) and the \(V_i\)’s)
- 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
- Define the important locations array as
important = [1] + V(length \(L=K+1\)). - 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.”
- Perform bit DP.
dp[mask][i]
= “the minimum cost when starting from location \(1\), having visited the set of destinations represented bymask, and currently being at destinationi(0-based)”
- Initialization:
dp[1<<i][i] = pair[0][i+1]
(going directly from \(1\) to each destination)
- Transition:
- From
dp[mask][i], move to an unvisited destinationj
dp[mask | (1<<j)][j] = min(..., dp[mask][i] + pair[i+1][j+1])
- From
- After full visitation
full=(1<<K)-1, add the cost of returning from each endpointito 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)\)
- bit DP is \(O(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]: continueinsidedijkstrais a standard optimization to discard stale heap entries.Pay attention to index correspondence:
pair[0]corresponds to location \(1\)pair[i+1]corresponds to destinationV[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.
投稿日時:
最終更新: