問題
$N$ 個の都市（番号 $0$ から $N-1$）があり、都市 $i$ から都市 $j$ への移動コスト $d_{i,j}$ が与えられる（$d_{i,j}=-1$ の場合、その方向への直接移動はできない）。
都市 $0$ を出発し、すべての都市をちょうど1回ずつ訪れて都市 $0$ に戻ってくる巡回路（ハミルトン閉路）のうち、総移動コストが最小のものを求めよ。そのような巡回路が存在しない場合は -1 のみを出力せよ。
入力形式
N
d_{0,0} ... d_{0,N-1}
...
d_{N-1,0} ... d_{N-1,N-1}制約
$2 \le N \le 15$
$-1 \le d_{i,j} \le 10^6$
$d_{i,i}=-1$
入出力例
入力例1
4
-1 10 15 20
10 -1 35 25
15 35 -1 30
20 25 30 -1出力例1
80
0 2 3 1 0入力例2
2
-1 5
-1 -1出力例2
-1概念図
ヒント（段階的開示）
ヒント1（方向性）
$N\le15$ は「全探索は間に合わないが$2^N$程度の指数時間は許容される」ことを示唆する。全順列$O(N!)$は間に合わないが、$2^{15}\times15^2$程度なら現実的。「これまでに訪れた都市の集合」を状態に持たせるとどうなるか。
ヒント2（アプローチ）
$dp[\text{mask}][i]$を「都市0から出発し、maskに含まれる都市を全て訪れ、現在都市iにいる」ときの最小コストと定義する。まだ訪れていない都市jへの遷移で更新する。答えは全都市訪問状態から都市0へ戻るコストを加えた最小値。経路復元には各状態に「直前にどこから来たか」を記録する。
ヒント3（誘導）
dp = [[INF] * N for _ in range(1 << N)]
par = [[-1] * N for _ in range(1 << N)]
dp[1][0] = 0
for mask in range(1, 1 << N):
if not (mask & 1):
continue
for i in range(N):
if not (mask >> i) & 1 or dp[mask][i] == INF:
continue
for j in range(N):
if (mask >> j) & 1 or cost[i][j] < 0:
continue
n_mask = mask | (1 << j)
n_cost = dp[mask][i] + cost[i][j]
if n_cost < dp[n_mask][j]:
dp[n_mask][j] = n_cost
par[n_mask][j] = i模範解答 (Python)
import sys
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
cost = []
for _ in range(N):
row = [int(data[idx + k]) for k in range(N)]
idx += N
cost.append(row)
INF = float('inf')
full = (1 << N) - 1
dp = [[INF] * N for _ in range(1 << N)]
par = [[-1] * N for _ in range(1 << N)]
dp[1][0] = 0
for mask in range(1, 1 << N):
if not (mask & 1):
continue
for i in range(N):
if not (mask >> i) & 1:
continue
cur = dp[mask][i]
if cur == INF:
continue
for j in range(N):
if (mask >> j) & 1:
continue
c = cost[i][j]
if c < 0:
continue
n_mask = mask | (1 << j)
n_cost = cur + c
if n_cost < dp[n_mask][j]:
dp[n_mask][j] = n_cost
par[n_mask][j] = i
best = INF
best_last = -1
for i in range(1, N):
if dp[full][i] == INF:
continue
c = cost[i][0]
if c < 0:
continue
total = dp[full][i] + c
if total < best:
best = total
best_last = i
if best == INF:
print(-1)
return
path = []
mask = full
i = best_last
while i != -1:
path.append(i)
pi = par[mask][i]
mask ^= (1 << i)
i = pi
path.reverse()
path.append(0)
print(best)
print(" ".join(map(str, path)))
main()Step-by-Step 解説
1状態設計「集合×現在地」
同じ「訪問済み集合・現在地」に何度も到達し得るため、これをメモ化の単位にする。集合はビットマスクで表現、状態数$2^N\times N$個。
同じ「訪問済み集合・現在地」に何度も到達し得るため、これをメモ化の単位にする。集合はビットマスクで表現、状態数$2^N\times N$個。
2遷移は「未訪問都市への1手」
まだ訪れていない都市への移動のみを考えることで、二重カウントや複数回訪問が構造的に発生しない。
まだ訪れていない都市への移動のみを考えることで、二重カウントや複数回訪問が構造的に発生しない。
3計算量
状態数$O(2^N N)$、各状態からの遷移$O(N)$で全体$O(2^N N^2)$。$N=15$で約$7.4\times10^6$、Pythonでも数秒以内。
状態数$O(2^N N)$、各状態からの遷移$O(N)$で全体$O(2^N N^2)$。$N=15$で約$7.4\times10^6$、Pythonでも数秒以内。
4答えの取り出しと経路復元
全都市訪問状態から都市0へ戻るコストを加えた最小値が答え。parを逆にたどって訪問順を復元する。
全都市訪問状態から都市0へ戻るコストを加えた最小値が答え。parを逆にたどって訪問順を復元する。
5存在しない場合の扱い
到達不能な都市があれば dp[full][i] や cost[i][0] が無効のままとなり、best が更新されず-1を出力する。
到達不能な都市があれば dp[full][i] や cost[i][0] が無効のままとなり、best が更新されず-1を出力する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 都市0を含まない状態も遷移元にしてしまう | 出発点固定なのに全マスクを無条件走査 | mask&1が0ならスキップする |
| d_{i,j}=-1（辺なし）を通常のコストとして加算 | 「辺がない」を表す番兵値であることを見落とす | 遷移前に必ずcost[i][j]<0をチェックしてスキップ |
| 経路復元時にmask更新順序を誤る | ビットを外す前に次を見てしまう | path追加→par参照→maskからビットを外す、の順を厳守 |
| N=2などの小さいコーナーケースを確認しない | 制約上N≥2だが往復辺の存在確認を怠る | N=2で往復両方の辺が存在するかだけの単純ケースも確認 |
| dp[1][0]=0の初期化を忘れる | 出発状態を明示せず全てINFのまま探索が進まない | 「都市0のみ訪問済み・現在地0・コスト0」を必ず初期化 |
次のステップ
- 発展: $N\le20$程度まで拡張したい場合、bitset演算やビット並列化、分枝限定法（MST下界やHeld-Karpの1-木下界、Day100-Q5参照）との組み合わせで実用的な高速化ができる。
- 発展2: 本問は非対称TSPとして設計した。対称TSPに限定した場合の高速化（状態を半分に減らす）を検討せよ。