巡回セールスマン問題をDPで解くプログラム

巡回セールスマン問題

atcoder abc301 E問題の解説を聞いたのを参考にしてなるべくコンパクトに巡回セールスマン問題をDPでとくプログラムをpython3で書いてみました。

以下が使ったデータです。
点０から出発してすべての点を通って０にもどることを考えています。

4
0 3 4 7
3 0 5 4
4 5 0 3
7 4 3 0

終わったときのｄｐは
[[0, 100, 100, 100],
[0, 100, 100, 100],
[100, 3, 100, 100],
[6, 3, 100, 100],
[100, 100, 4, 100],
[8, 100, 4, 100],
[100, 9, 8, 100],
[12, 9, 8, 100],
[100, 100, 100, 7],
[14, 100, 100, 7],
[100, 11, 100, 7],
[14, 11, 100, 7],
[100, 100, 10, 7],
[14, 100, 10, 7],
[100, 11, 10, 11],
[14, 11, 10, 11]]
となっています。

プログラム

tsp.py

n=int(input())
dist=[[int(i) for i in input().split()] for _ in range(n)]
print(n,dist)
inf=100
n2=1<<n
dp=[[inf]*n for _ in range(n2)]
dp[0][0]=0
#print(dp)
for s in range(n2):        # sでビット全探索
  for u in range(n):       # uが始点
    if dp[s][u]==inf:      # uが有限値ではないとき
      continue
    for v in range(n):     # vが終点
      if ~s>>v&1:          # vがsに含まれないとき
        dp[s|1<<v][v]=min(dp[s|1<<v][v],dp[s][u]+dist[u][v])
print(dp)