E - 配達員の巡回 / Delivery Person's Round Editorial by admin
GPT 5.4 High概要
地点 \(1\) と \(K\) 個の届け先だけに注目し、それらの間の最短距離を先に求めます。
すると問題は「地点 \(1\) から出発して全届け先を 1 回以上訪れ、再び \(1\) に戻る最短巡回」を求める問題になり、これは \(K \le 15\) を活かした bit DP で解けます。
考察
この問題では、実際の経路中で同じ地点や同じ道を何度通ってもよいです。
そのため一見すると、
- どの順で届け先を回るか
- 途中でどの道を通るか
- どこを経由して戻るか
を全部考えなければならず、かなり複雑に見えます。
重要な気づき 1: 順番さえ決まれば、区間ごとは最短経路でよい
たとえば、届け先を訪れる順番が
\(1 \to V_3 \to V_1 \to V_2 \to 1\)
に決まっているとします。
このとき、\(1\) から \(V_3\) へ行く部分、\(V_3\) から \(V_1\) へ行く部分、… は、それぞれ最短経路を使うのが最善です。
つまり、その順番で回る最小コストは
\( \mathrm{dist}(1, V_3) + \mathrm{dist}(V_3, V_1) + \mathrm{dist}(V_1, V_2) + \mathrm{dist}(V_2, 1) \)
になります。
ここで \(\mathrm{dist}(u,v)\) は元のグラフ上での最短距離です。
したがって、元の大きなグラフ全体を直接扱う代わりに、
- 特別な点:\(1, V_1, V_2, \dots, V_K\)
の間の最短距離だけ分かれば十分です。
重要な気づき 2: 必要なのは「特別な点同士の最短距離」だけ
地点数 \(N\) は最大 \(5 \times 10^4\) なので、全点対最短路(Floyd-Warshall など)は不可能です。
しかし、必要なのは \(K+1 \le 16\) 個の特別な点同士の距離だけです。
辺の重みは正なので、各特別な点から Dijkstra 法を 1 回ずつ行えば十分です。
これで
- \(1\) から各届け先への最短距離
- 各届け先同士の最短距離
が求まります。
重要な気づき 3: 届け先の回り方は bit DP で管理できる
ここまでで、問題は次のように言い換えられます。
- 始点は \(1\)
- \(K\) 個の届け先をすべて訪れる
- 最後に \(1\) に戻る
- 移動コストは特別な点同士の最短距離
これは典型的な「巡回順序」の問題なので、
\(K \le 15\) を使って bit DP ができます。
素朴な方法がなぜだめか
1. 届け先の順列を全探索する
届け先の順番を全列挙すると \(K!\) 通りです。
\(K=15\) では
\( 15! \approx 1.3 \times 10^{12} \)
となり、到底間に合いません。
2. 全点対最短路を求める
\(N\) が最大 \(5 \times 10^4\) なので、\(O(N^3)\) は完全に不可能です。
どう解決するか
- 特別な点 \(1, V_1, \dots, V_K\) からだけ Dijkstra を行い、必要な最短距離だけ求める
- その後、届け先集合を bit で持つ DP で最小巡回コストを求める
この 2 段階で、制約内に収まります。
アルゴリズム
1. グラフを作る
道路は双方向なので、隣接リストを両方向に追加します。
2. 特別な点同士の最短距離を Dijkstra で求める
特別な点を
\( \text{special} = [1, V_1, V_2, \dots, V_K] \)
とします。
各 special から Dijkstra を行い、他の special への最短距離だけを取り出します。
これで \(S = K+1\) 個の点同士の距離表 pair ができます。
コードでは dijkstra(src) が
srcから全頂点への最短距離を求めつつ- special に属する頂点への距離だけ
resに記録
しています。
また、必要なのは special への距離だけなので、
全 special への最短距離が確定したら探索を打ち切ることで少し高速化しています。
3. bit DP をする
以下の DP を定義します。
\( dp[\text{mask}][i] \)
= 「地点 \(1\) を出発し、mask で表される届け先集合を訪問済みで、最後に \(V_i\) にいるときの最小コスト」
ここで mask は \(K\) ビットの整数で、
\(j\) 番目の bit が 1 なら \(V_j\) を訪問済みです。
初期値
最初に 1 つだけ届け先 \(V_i\) を訪れる場合は
\( dp[1 \ll i][i] = \mathrm{dist}(1, V_i) \)
です。
遷移
今 \(V_i\) にいて、まだ訪れていない \(V_j\) へ次に行くなら
$
dp[\text{mask} \cup {j}][j]
\min\left( dp[\text{mask}][i] + \mathrm{dist}(V_i, V_j) \right) $
となります。
最終答え
すべての届け先を訪問した後、最後に \(V_i\) から \(1\) へ戻るので
\( \min_i \left( dp[(1 \ll K)-1][i] + \mathrm{dist}(V_i, 1) \right) \)
が答えです。
なぜこれで正しいか
任意の最適な経路を考え、各届け先を初めて訪れた順番だけを取り出します。
すると、その順番は
\( 1 \to V_{p_1} \to V_{p_2} \to \cdots \to V_{p_K} \to 1 \)
の形になります。
このとき、連続する 2 点の間の移動は、元の経路では何を通っていてもよいですが、
そこを最短経路に置き換えてもコストは増えません。
したがって、最適解は「特別な点同士の最短距離を辺重みとする完全グラフ上の巡回問題」として考えてよいです。
そして、その巡回問題を bit DP で全ての訪問集合・最後の点について最小化しているので、答えが求まります。
計算量
- 時間計算量: \(O((K+1)\, M \log N + K^2 2^K)\)
- 空間計算量: \(O(N + M + K 2^K)\)
補足
- Dijkstra を \(K+1\) 回行うので \(O((K+1) M \log N)\)
- DP は状態数が \(2^K \times K\)、各状態から最大 \(K\) 個遷移するので \(O(K^2 2^K)\)
\(K \le 15\) なので、bit DP は十分間に合います。
実装のポイント
- 辺の重みや答えは大きくなるので、
INF = 10**30のような十分大きい値を使う - Dijkstra は重み付きグラフなので BFS ではなく優先度付きキュー付きのものを使う
- 必要なのは special 同士の距離だけなので、Dijkstra の結果を全部保存せず special への距離だけ抜き出す
- bit DP では「まだ訪れていない届け先」を bit 演算で高速に列挙している
特にこのコードでは、
rem & -rem で最下位の 1 ビットを取り出し、未訪問の届け先を効率よく回しています。
ソースコード
import sys
import heapq
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
N = next(it)
M = next(it)
K = next(it)
V = [next(it) for _ in range(K)]
g = [[] for _ in range(N + 1)]
for _ in range(M):
a = next(it)
b = next(it)
c = next(it)
g[a].append((b, c))
g[b].append((a, c))
special = [1] + V
S = K + 1
INF = 10**30
sp_idx = [-1] * (N + 1)
for i, v in enumerate(special):
sp_idx[v] = i
heappush = heapq.heappush
heappop = heapq.heappop
def dijkstra(src):
dist = [INF] * (N + 1)
dist[src] = 0
res = [INF] * S
found = 0
pq = [(0, src)]
while pq and found < S:
d, v = heappop(pq)
if d != dist[v]:
continue
idx = sp_idx[v]
if idx != -1 and res[idx] == INF:
res[idx] = d
found += 1
for to, w in g[v]:
nd = d + w
if nd < dist[to]:
dist[to] = nd
heappush(pq, (nd, to))
return res
pair = [dijkstra(s) for s in special]
d0 = pair[0][1:]
dt = [pair[i + 1][1:] for i in range(K)]
allmask = (1 << K) - 1
dp = [[INF] * K for _ in range(1 << K)]
for i in range(K):
dp[1 << i][i] = d0[i]
bit_to_idx = [0] * (1 << K)
for i in range(K):
bit_to_idx[1 << i] = i
for mask in range(1 << K):
rem_base = allmask ^ mask
if rem_base == 0:
continue
row = dp[mask]
for i in range(K):
cur = row[i]
if cur == INF:
continue
di = dt[i]
rem = rem_base
while rem:
lsb = rem & -rem
j = bit_to_idx[lsb]
nd = cur + di[j]
nrow = dp[mask | lsb]
if nd < nrow[j]:
nrow[j] = nd
rem ^= lsb
ans = INF
final_row = dp[allmask]
for i in range(K):
cand = final_row[i] + d0[i]
if cand < ans:
ans = cand
print(ans)
if __name__ == "__main__":
main()
この解説は gpt-5.4-high によって生成されました。