AcWing 91. 最短Hamilton路径（状态压缩DP+哈密顿回路）

题目链接

https://www.acwing.com/problem/content/description/93/

思路

这道题看似像一个最短路，但是并不是，因为我们要求对于每一个点都经过，但是最短路不能保证，所以我们换一个思路用DP，我们定义 f [ i ] [ j ] f[i][j] f[i][j]表示从0走到j，走过的所有点是i状态的最短路径，其中的i我们将其看为二进制表示，对于每一位我们用1表示这一个点走过，用0表示这一个点没走过，那么我们要经过第一个点是0，所以我们初始化 f [ 1 ] [ 0 ] = 0 f[1][0] = 0 f[1][0]=0表示走到0这个点花费的路径价值为0，然后假设倒数第二个点为 k k k那么我们要求的其实就是 s − > k − > j s->k->j s−>k−>j的一个路径最小值，对于 k − > j k->j k−>j的路径我们已经固定了即 w [ k ] [ j ] w[k][j] w[k][j]，那么从 s − > k s->k s−>k的一个距离最短值就需要从前面的状态转移过来即： f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i − ( 1 < < j ) ] [ k ] + w [ k ] [ j ] ) f[i][j]=min(f[i][j],f[i-(1