E - 配達員の巡回 / Delivery Person's Round Editorial by admin Editorial for printing
Claude 4.6 Opus (Thinking)概要
地点 \(1\) を出発し、\(K\) 個の届け先すべてを訪れて地点 \(1\) に戻る最短経路を求める問題です。\(K \leq 15\) という制約から、巡回セールスマン問題(TSP)をビットマスク DP で解きます。
考察
素朴なアプローチとその問題点
\(K\) 個の届け先を訪れる順番は \(K!\) 通りあります。\(K = 15\) のとき \(15! \approx 1.3 \times 10^{12}\) となり、全列挙は到底間に合いません。
重要な気づき
中間地点は無視できる: 地点 \(1\) と \(K\) 個の届け先、合わせて \(K+1\) 個の「重要な地点」だけに注目すればよいです。重要な地点間の移動は、元のグラフ上の最短経路で行えばよく、途中の経路は気にする必要がありません。
距離行列の事前計算: 各重要な地点から Dijkstra 法を実行すれば、重要な地点間の最短距離をすべて求められます。これにより問題は「\((K+1)\) 頂点の完全グラフ上の TSP」に帰着されます。
ビットマスク DP: \(K \leq 15\) なので、「どの届け先を訪問済みか」を \(K\) ビットの整数で表現し、DP で最適な訪問順を求められます。状態数は \(2^K \times (K+1)\) で、\(K=15\) のとき約 \(50\) 万程度です。
アルゴリズム
ステップ 1: 最短距離の前計算
重要な地点は地点 \(1\) と届け先 \(V_1, \ldots, V_K\) の計 \(K+1\) 個です。それぞれの地点を始点として Dijkstra 法を実行し、全頂点への最短距離を求めます。これにより、重要な地点同士の距離行列 \(\text{key\_dist}[i][j]\) が得られます。
ステップ 2: ビットマスク DP による TSP
- 状態: \(dp[\text{mask}][u]\) = 届け先の訪問状態が \(\text{mask}\) で、現在重要な地点 \(u\) にいるときの最小コスト
- 初期状態: \(dp[0][0] = 0\)(地点 \(1\) にいて、どの届け先もまだ訪問していない)
- 遷移: 状態 \((\text{mask}, u)\) から、まだ訪問していない届け先 \(j\) に移動する:
\[dp[\text{mask} \mid (1 \ll j)][j+1] = \min\left(dp[\text{mask} \mid (1 \ll j)][j+1],\; dp[\text{mask}][u] + \text{key\_dist}[u][j+1]\right)\]
- 答え: 全届け先を訪問した状態 \(\text{full\_mask} = 2^K - 1\) で、地点 \(1\) に戻るコストを加算した最小値:
\[\text{ans} = \min_{u} \left( dp[\text{full\_mask}][u] + \text{key\_dist}[u][0] \right)\]
計算量
- 時間計算量: \(O((K+1) \cdot (N + M) \log N + 2^K \cdot K^2)\)
- Dijkstra を \(K+1\) 回実行: \(O((K+1) \cdot (N + M) \log N)\)
- ビットマスク DP: \(O(2^K \cdot K^2)\)(各状態から最大 \(K\) 個の遷移)
- \(K = 15, N = M = 5 \times 10^4\) で十分高速
- 空間計算量: \(O((K+1) \cdot N + 2^K \cdot K)\)
- Dijkstra の距離配列: \(O((K+1) \cdot N)\)
- DP テーブル: \(O(2^K \cdot (K+1))\)
実装のポイント
重要な地点のインデックス管理: 地点 \(1\) をインデックス \(0\)、届け先 \(V_i\) をインデックス \(i\)(\(1 \leq i \leq K\))として管理すると、ビットマスクの \(j\) ビット目が届け先 \(V_{j+1}\)(キーノードインデックス \(j+1\))に対応し、混乱を避けられます。
高速入力: Python では
sys.stdin.buffer.read()でまとめて読み込むことで、大量入力時の速度を改善できます。無限大の扱い: 到達不能な状態を
float('inf')で初期化し、遷移時にスキップすることで不要な計算を避けます。ソースコード
import heapq
import sys
def dijkstra(graph, start, N):
dist = [float('inf')] * (N + 1)
dist[start] = 0
hq = [(0, start)]
while hq:
d, u = heapq.heappop(hq)
if d > dist[u]:
continue
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(hq, (nd, v))
return dist
def main():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
M = int(input_data[idx]); idx += 1
K = int(input_data[idx]); idx += 1
V = []
for i in range(K):
V.append(int(input_data[idx])); idx += 1
graph = [[] for _ in range(N + 1)]
for i in range(M):
a = int(input_data[idx]); idx += 1
b = int(input_data[idx]); idx += 1
c = int(input_data[idx]); idx += 1
graph[a].append((b, c))
graph[b].append((a, c))
# Key nodes: node 1 (index 0) and V[0..K-1] (indices 1..K)
key_nodes = [1] + V # length K+1
# Compute shortest paths from each key node
# dist_from[i] = shortest distance array from key_nodes[i]
dist_from = []
for node in key_nodes:
dist_from.append(dijkstra(graph, node, N))
# Build distance matrix between key nodes
# key_dist[i][j] = shortest distance from key_nodes[i] to key_nodes[j]
num_keys = K + 1
key_dist = [[0] * num_keys for _ in range(num_keys)]
for i in range(num_keys):
for j in range(num_keys):
key_dist[i][j] = dist_from[i][key_nodes[j]]
# TSP with bitmask DP
# State: (visited subset of delivery nodes (bits 0..K-1 for V[0]..V[K-1]), current key node index)
# We need to visit all K delivery nodes and return to node 0 (which is key_nodes[0] = 1)
full_mask = (1 << K) - 1
INF = float('inf')
# dp[mask][i] = min cost to have visited the delivery nodes in mask, currently at key node i
# i ranges from 0 to K (0 = node 1, 1..K = delivery nodes)
dp = [[INF] * num_keys for _ in range(1 << K)]
# Start at key node 0 (node 1), no deliveries done
dp[0][0] = 0
for mask in range(1 << K):
for u in range(num_keys):
if dp[mask][u] == INF:
continue
cur_cost = dp[mask][u]
# Try going to each delivery node
for j in range(K):
if mask & (1 << j):
continue
v = j + 1 # key node index for V[j]
new_mask = mask | (1 << j)
new_cost = cur_cost + key_dist[u][v]
if new_cost < dp[new_mask][v]:
dp[new_mask][v] = new_cost
# Find minimum cost: visit all deliveries then return to node 1
ans = INF
for u in range(num_keys):
if dp[full_mask][u] == INF:
continue
total = dp[full_mask][u] + key_dist[u][0]
if total < ans:
ans = total
print(ans)
if __name__ == '__main__':
main()
この解説は claude4.6opus-thinking によって生成されました。
posted:
last update: