91 AcWing 最短Hamilton路径

题意

https://www.acwing.com/problem/content/93/ 原题链接

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数n。

接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。

对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式
输出一个整数，表示最短Hamilton路径的长度。

数据范围
1≤n≤20
0≤a[i,j]≤107

解题思路

参考思路 https://www.acwing.com/solution/content/1037/

NP Hard问题，暴力时间复杂度O(n?n!)O(n?n!)
这题正解其实是利用状压DP的方法来做，状态转移方程为

dp[i][j] = min{dp[i][j], dp[i - (1 << j)][k] + map[k][j]}
其中map数组为权值，map[k][j]是点k到点j的权值

dp[i][j]表示当前已经走过点的集合为i，移动到j。所以这个状态转移方程就是找一个中间点k，将已经走过点的集合i中去除掉j（表示j不在经过的点的集合中），然后再加上从k到j的权值

问题在于如何表达已经走过点的集合i，其实很简单，假如走过0,1,4这三个点，我们用二进制10011就可以表示，2,3没走过所以是0

那么走过点的集合i中去除掉点j也很容易表示i - (1 << j)，比方说i是{0,1,4}，j是1，那么i = 10011，(1 << j) = 10，i - (1 << j) = 10001

那么问题的答案就应该是dp[01....111][n-1]，表示0~n-1都走过，且当前移动到n-1这个点

分析一下时间复杂度，n为20的时候，外层循环(1<<20)，内层循环20，所以整体时间复杂度O(20?220)，这比O(n?n!)快多了

作者：数学家是我理想
链接：https://www.acwing.com/solution/content/1037/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现

#include
#include
#include
#include
#include
#include
#include
#include
#include