前言
传送门 :
思路
我们使用 二进制状态表示当前经过的点集
状态表示
f
[
s
t
a
t
e
]
[
i
]
f[state][i]
f[state][i] 经过点集
s
t
a
t
e
state
state并且到达
i
i
i点的 最短路径长度
状态计算
f
[
s
t
a
t
e
]
[
j
]
=
m
i
n
(
f
[
s
t
a
t
e
]
[
j
]
,
f
[
s
t
a
t
e
]
[
k
]
+
w
[
k
]
[
j
]
)
f[state][j] = min(f[state][j],f[state][k]+w[k][j])
f[state][j]=min(f[state][j],f[state][k]+w[k][j])
如果去掉 j j j的时候,还可以通过 k k k转移到 j j j的话,那么我们进行转移
技巧 :
使用异或操作去掉当前状态中的某一个位置
s
t
a
t
e
⊕
(
1
<
<
j
)
state \oplus(1
