板刷蓝书

最短Hamilton路径

状压 dp。设 \(f_{S,i}\) 表示走过的节点状态为 \(S\)\((0\) 为没走过，\(1\) 为走过 \()\)，当前在点 \(i\) 时的最小代价，显然 \(S\) 的第 \(i\) 位必须为 \(1\)。

那么 \(f_{S,i}= \min_{S \operatorname{and} 2^j =1,j \neq i } \lbrace f_{S \operatorname {xor} 2^i,j}+dis_{j,i}\rbrace \)。

意思就是枚举在走 \(i\) 号点之前走的是哪个点，由上个没走过 \(i\) 的状态加上两点的距离转移过来。

注意这里点的编号都从 \(0\) 开始，最后输出 \(f_{2^n-1,n-1}\) 即可。