E - 配達員の巡回 / Delivery Person's Round Editorial by admin Editorial for printing
gpt-5.3-codex概要
「地点 \(1\) から出発して、指定された \(K\) 個の届け先をすべて回って \(1\) に戻る最短時間」を求める問題です。
本質は、重要な地点間の最短距離を先に求めてから、\(K \le 15\) を活かした bit DP(巡回セールスマン型DP)で解くことです。
考察
この問題で厄介なのは、グラフ全体の頂点数 \(N,M\) が最大 \(5\times 10^4\) と大きい一方、必ず訪れるべき届け先は \(K\le 15\) と小さいことです。
まず素朴に「グラフ上で状態を持って探索(今どこにいて、どの届け先を訪問済みか)」をすると、状態数が \(N \times 2^K\) になり大きすぎます。
最大で \(5\times 10^4 \times 2^{15}\) となり、現実的ではありません。
ここで重要な観察は次の通りです。
- 実際に最適化したいのは「地点 \(1\) と届け先 \(K\) 個」だけ(合計 \(K+1\) 個)
- それらの間の移動コストは、元グラフ上の最短距離に置き換えてよい
(最短経路同士をつないでも、三角不等式により損しない)
つまり、元グラフを直接DPするのではなく、
- 重要地点(\(1\) と \(V_i\) たち)間の最短距離行列を作る
- その完全グラフ上で「全届け先を回って戻る最小コスト」を bit DP で解く
という二段構えにすれば高速に解けます。
アルゴリズム
- 重要地点配列を
important = [1] + Vとする(長さ \(L=K+1\))。 - 各重要地点を始点にダイクストラを実行し、他の重要地点までの最短距離を
pair[i][j]に記録する。- これで「重要地点間の距離表」が完成。
- bit DP を行う。
dp[mask][i]
= 「地点 \(1\) から出発し、maskで表される届け先集合を訪問済みで、最後に届け先i(0-based)にいるときの最小コスト」
- 初期化:
dp[1<<i][i] = pair[0][i+1]
(\(1\) から各届け先へ直接行く)
- 遷移:
dp[mask][i]から未訪問jに移る
dp[mask | (1<<j)][j] = min(..., dp[mask][i] + pair[i+1][j+1])
- 全訪問
full=(1<<K)-1の後、各終点iから地点 \(1\) に戻るコストを足して最小値を取る。ans = min(dp[full][i] + pair[i+1][0])
これがコード中の処理と一致しています。
計算量
- 時間計算量:
ダイクストラを \(K+1\) 回行うので
\(O((K+1)\, M \log N)\)
- bit DP が \(O(2^K K^2)\)
よって全体は
\(O((K+1)M\log N + 2^K K^2)\)
- bit DP が \(O(2^K K^2)\)
- 空間計算量:
グラフ \(O(N+M)\)、距離表 \(O((K+1)^2)\)、DP表 \(O(2^K K)\)
合計で \(O(N+M+2^K K)\)
実装のポイント
辺重みが正なので最短路はダイクストラでOK。
距離や答えは最大で大きくなるため、
INF = 10**30のように十分大きい値を使う。dijkstra内のif d != dist[v]: continueは、古いヒープ要素を捨てる定番高速化。インデックス対応に注意:
pair[0]が地点 \(1\)pair[i+1]が届け先V[i]
最後に「戻るコスト(終点→1)」を必ず足すのを忘れない。
ソースコード
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()
この解説は gpt-5.3-codex によって生成されました。
posted:
last update: