[Acwing] 91. 最短Hamilton路径 状态压缩dp

前言

传送门 :

思路

我们使用 二进制状态表示当前经过的点集

状态表示 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