E - 配達員の巡回 / Delivery Person's Round Editorial by admin
Gemini 3.0 Flash (Thinking)概要
この問題は、地点 1 を出発して \(K\) 個の指定された地点をすべて巡回し、再び地点 1 に戻る際の最短経路を求める問題です。 地点数 \(N\) や道の数 \(M\) は大きいですが、巡回すべき地点の数 \(K\) が最大 15 と非常に小さいことが特徴です。
考察
1. 必要な情報の整理
地点は \(N\) 個ありますが、私たちが特に関心があるのは「地点 1」と「届け先の \(K\) 個の地点」の合計 \(K+1\) 個の地点だけです。 地点 \(A\) から地点 \(B\) へ移動する際、その途中にある他の地点が届け先でなければ、単に最短経路で通過すればよいことになります。
したがって、この問題は以下の 2 ステップに分解できます。 1. 地点 1 および \(V_1, \dots, V_K\) の間の全ペア間の最短距離を求める。 2. 求めた距離を用いて、いわゆる巡回セールスマン問題 (TSP) を解く。
2. なぜ素朴な方法ではダメなのか
巡回する順番を全探索しようとすると、その組み合わせは \(K!\) 通りになります。\(K=15\) のとき \(15! \approx 1.3 \times 10^{12}\) となり、制限時間内に計算が終わりません。 そこで、動的計画法(DP)を用いることで、この計算量を \(O(2^K \cdot K^2)\) 程度に抑えることができます。\(2^{15} \cdot 15^2 \approx 7.3 \times 10^6\) であり、これなら十分に間に合います。
アルゴリズム
ステップ 1: 全ペア間の最短距離の計算
地点 1 と各届け先 \(V_i\)(合計 \(K+1\) 箇所)を始点として、それぞれダイクストラ法を実行します。
- 1 回のダイクストラ法で、ある始点から他のすべての地点への最短距離が求まります。
- これを \(K+1\) 回繰り返すことで、必要な地点間の距離をすべて網羅した \((K+1) \times (K+1)\) の距離行列 dist_matrix を作成します。
ステップ 2: ビット DP による巡回セールスマン問題
「どの地点を訪れたか」という集合をビットマスク(整数値)で表し、以下の DP を行います。
DPの状態定義:
dp[mask][i]:= すでに訪れた届け先の集合がmaskであり、現在地が届け先 \(V_i\) であるときの最小コスト (※maskは \(K\) ビットの整数で、\(j\) 番目のビットが 1 なら \(V_j\) を訪問済みであることを示します)初期状態: 地点 1 から各届け先 \(V_i\) へ直接向かうコストを入れます。
dp[1 << i][i] = dist_matrix[0][i+1](0は地点 1、i+1は \(V_i\) に対応)遷移: 現在の状態
dp[mask][i]から、まだ訪れていない届け先 \(V_j\) へ移動する場合:dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist_matrix[i+1][j+1])最終回答: すべての届け先を訪れた状態
dp[(1 << K) - 1][i]に、現在地 \(V_i\) から地点 1 に戻るコストdist_matrix[i+1][0]を加えたものの最小値が答えとなります。
計算量
- 時間計算量: \(O(K(N + M) \log N + 2^K \cdot K^2)\)
- ダイクストラ法 \(K+1\) 回分:\(O(K(N + M) \log N)\)
- ビット DP 部分:\(O(2^K \cdot K^2)\)
- 空間計算量: \(O(N + M + 2^K \cdot K)\)
- グラフの隣接リスト、ダイクストラ法の距離配列、DP テーブルの保持に必要なメモリです。
実装のポイント
ダイクストラ法の効率化: ダイクストラ法を実行する際、その回の始点から「関心のある \(K+1\) 個の地点」すべてへの距離が確定した時点で探索を打ち切る(
breakする)ことで、実行時間を短縮できます。高速な入出力: \(N, M\) が大きいため、Python では
sys.stdin.read().split()などを用いて一括で入力を読み込むのが効果的です。ビット演算:
mask & (1 << j)で訪問済み判定、mask | (1 << j)で訪問フラグを立てる操作など、ビット演算を正確に行う必要があります。ソースコード
import heapq
import sys
def solve():
# Use fast I/O to read all input at once
input_data = sys.stdin.read().split()
if not input_data:
return
# N: number of locations, M: number of roads, K: number of destinations
N = int(input_data[0])
M = int(input_data[1])
K = int(input_data[2])
# V: list of destination locations
V = [int(x) for x in input_data[3:3+K]]
# Build adjacency list for the graph
adj = [[] for _ in range(N + 1)]
idx = 3 + K
for _ in range(M):
u = int(input_data[idx])
v = int(input_data[idx+1])
w = int(input_data[idx+2])
adj[u].append((v, w))
adj[v].append((u, w))
idx += 3
# The locations we are interested in: starting point (1) and all destinations (V)
nodes = [1] + V
num_nodes = K + 1
# Precompute shortest paths between all pairs of interest using Dijkstra
# We run Dijkstra from each of the K+1 nodes.
dist_matrix = [[0] * num_nodes for _ in range(num_nodes)]
is_target = [False] * (N + 1)
for node in nodes:
is_target[node] = True
for i in range(num_nodes):
start_node = nodes[i]
dists = [float('inf')] * (N + 1)
dists[start_node] = 0
pq = [(0, start_node)]
count = 0
visited_targets = [False] * (N + 1)
while pq:
d, u = heapq.heappop(pq)
if d > dists[u]:
continue
# If we popped a node of interest, record it.
# Once we've popped all interest nodes, we can stop Dijkstra for this start_node.
if is_target[u] and not visited_targets[u]:
visited_targets[u] = True
count += 1
if count == num_nodes:
break
for v, w in adj[u]:
new_d = d + w
if dists[v] > new_d:
dists[v] = new_d
heapq.heappush(pq, (new_d, v))
# Fill the distance matrix for the interest nodes
for j in range(num_nodes):
dist_matrix[i][j] = dists[nodes[j]]
# TSP using Bitmask DP
# dp[mask][i] is the minimum distance to visit the set of destinations in 'mask',
# ending at destination V[i].
# 'mask' is a bitmask of length K where the j-th bit represents destination V[j].
INF = float('inf')
dp = [[INF] * K for _ in range(1 << K)]
# Initial step: move from location 1 (nodes[0]) to each destination V[i] (nodes[i+1])
for i in range(K):
dp[1 << i][i] = dist_matrix[0][i+1]
# Iterate through all masks (sets of visited destinations)
for mask in range(1, 1 << K):
dp_mask = dp[mask]
for i in range(K):
d_curr = dp_mask[i]
if d_curr == INF:
continue
# Try moving from the current destination V[i] to a next destination V[j]
dist_row = dist_matrix[i+1]
for j in range(K):
if not (mask & (1 << j)):
new_mask = mask | (1 << j)
new_dist = d_curr + dist_row[j+1]
if dp[new_mask][j] > new_dist:
dp[new_mask][j] = new_dist
# Final step: from the last visited destination back to location 1
ans = INF
full_mask = (1 << K) - 1
dist_from_start = dist_matrix[0] # dist_matrix is symmetric, dist_matrix[0][i+1] == dist_matrix[i+1][0]
dp_full = dp[full_mask]
for i in range(K):
# Total cycle: 1 -> ... -> V[i] -> 1
res = dp_full[i] + dist_from_start[i+1]
if res < ans:
ans = res
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3-flash-thinking によって生成されました。