E - 配送計画 / Delivery Plan Editorial by admin
claude4.8opus-high概要
地点 \(1\) から出発し、指定された \(K\) 個の届け先をすべて訪問してから地点 \(N\) に到着するまでの最小移動時間を求める問題です。届け先を訪れる順番は自由に選べます。これは「巡回セールスマン問題（TSP）」を最短経路と組み合わせた典型問題です。
考察
重要な観察 1: 順番の最適化が必要
届け先を訪れる順番は自由なので、\(K\) 個の届け先をどの順番で回るかをすべて試す必要があります。素朴に全順列を試すと \(O(K!)\) 通りあり、\(K = 15\) では \(15! \approx 1.3 \times 10^{12}\) となり、到底間に合いません。
そこで、bitDP（ビットマスクを使った動的計画法） を使い、\(O(2^K \cdot K^2)\) で順番の最適化を行います。
重要な観察 2: 地点間の最短距離だけが重要
途中で届け先以外の地点を自由に通過でき、同じ地点・道路を何度通ってもよいので、
- 「地点 \(1\) → ある届け先」
- 「ある届け先 → 別の届け先」
- 「ある届け先 → 地点 \(N\)」
の各移動コストは、グラフ上の最短経路（最短距離） に置き換えてよいことがわかります。つまり、元のグラフを「重要な地点（地点 \(1\)、各届け先、地点 \(N\)）だけからなる完全グラフ」に圧縮し、その上でTSPを解けばよいのです。
距離の計算方法
必要な最短距離は次の通りです。
- 地点 \(1\) から各届け先 \(C_i\) までの距離
- 各届け先 \(C_i\) から別の届け先 \(C_j\) までの距離
- 各届け先 \(C_i\) から地点 \(N\) までの距離
これらは、各届け先 \(C_i\) を始点としたダイクストラ法を \(K\) 回、加えて地点 \(1\) を始点としたダイクストラ法を \(1\) 回行うことですべて求められます（道路は双方向なので \(C_i\) から \(N\) への距離は \(C_i\) 始点のダイクストラで得られます）。
合計 \(K + 1\) 回のダイクストラ法を実行します。
アルゴリズム
ステップ1: 最短距離の前計算
- 地点 \(1\) を始点にダイクストラ →
start_to[i]（地点 \(1\) から \(C_i\) への距離） - 各 \(C_i\) を始点にダイクストラ →
dd[i][j]（\(C_i\) から \(C_j\) への距離）to_N[i]（\(C_i\) から地点 \(N\) への距離）
ステップ2: bitDP
dp[mask][i] を「これまでに mask で表される届け先集合をすべて訪問済みで、最後に訪れた届け先が \(i\) であるときの、地点 \(1\) からの最小移動時間」と定義します。
初期化: 最初に訪れる届け先が \(i\) の場合、 $\(dp[\{i\}][i] = \text{start\_to}[i]\)$
遷移: 状態 \((mask, i)\) から、まだ訪れていない届け先 \(j\) へ移動する場合、 $\(dp[mask \cup \{j\}][j] \leftarrow \min\big(dp[mask \cup \{j\}][j],\ dp[mask][i] + dd[i][j]\big)\)$
答え:
すべての届け先を訪問した状態 full（\(=2^K - 1\)）から、最後の届け先 \(i\) を経て地点 \(N\) へ向かう最小値を取ります。
$\(\text{ans} = \min_i \big(dp[full][i] + \text{to\_N}[i]\big)\)$
計算量
- ダイクストラ法を \(K + 1\) 回実行: \(O\big((K+1)(M + N)\log N\big)\)
- bitDP: \(O(2^K \cdot K^2)\)
これらを合わせて、
- 時間計算量: \(O\big(K (M + N) \log N + 2^K K^2\big)\)
- 空間計算量: \(O\big(K N + 2^K K\big)\)
\(K \le 15\) なので \(2^K K^2 \approx 7.4 \times 10^6\)、ダイクストラ部分も十分高速で、制約内に収まります。
実装のポイント
距離は非常に大きくなる: \(W_i\) は最大 \(10^9\)、経路は複数の届け先をまたぐため、距離の合計は \(64\) ビット整数の範囲が必要です。Pythonでは多倍長整数なのでオーバーフローの心配はありませんが、C++などでは
long longを使う必要があります。無効な状態のスキップ: bitDPの遷移では、
dp[mask][i]がINF（到達不能）の場合や、\(i\) がmaskに含まれない場合をスキップすることで無駄な計算を省きます。入力の高速読み込み: \(N, M\) が大きいので、
sys.stdin.buffer.read()でまとめて読み込むと高速です。ダイクストラはヒープ（優先度付きキュー）で実装:
heapqを用い、取り出した距離が記録済みの距離より大きい場合（古い情報）はスキップする定石を使っています。ソースコード
import sys
import heapq
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
K = int(data[idx]); idx += 1
adj = [[] 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
adj[u].append((v, w))
adj[v].append((u, w))
C = [int(data[idx + i]) for i in range(K)]
idx += K
INF = float('inf')
def dijkstra(start):
dist = [INF] * (N + 1)
dist[start] = 0
h = [(0, start)]
while h:
d, u = heapq.heappop(h)
if d > dist[u]:
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(h, (nd, v))
return dist
# distances from start node 1
d_start = dijkstra(1)
start_to = [d_start[C[i]] for i in range(K)]
# distances from each delivery
dd = [None] * K
to_N = [0] * K
delivery_dist = []
for i in range(K):
di = dijkstra(C[i])
delivery_dist.append(di)
to_N[i] = di[N]
dd = [[delivery_dist[i][C[j]] for j in range(K)] for i in range(K)]
full = (1 << K) - 1
dp = [[INF] * K for _ in range(1 << K)]
for i in range(K):
dp[1 << i][i] = start_to[i]
for mask in range(1 << K):
row = dp[mask]
for i in range(K):
if not (mask >> i) & 1:
continue
cur = row[i]
if cur == INF:
continue
ddi = dd[i]
for j in range(K):
if (mask >> j) & 1:
continue
nd = cur + ddi[j]
nm = mask | (1 << j)
if nd < dp[nm][j]:
dp[nm][j] = nd
ans = INF
for i in range(K):
v = dp[full][i] + to_N[i]
if v < ans:
ans = v
print(ans)
main()
この解説は claude4.8opus-high によって生成されました。