题目链接
思路：基本状压dp
看题目知道此题求的是最短哈密顿路径，也就是一条从1到n的经过所有点的最短路径。
我们可以使用状态压缩，使用一个二进制数state代表一种状态，state代表经过的所有点的集合。
例如
state=1，代表只经过1号点。
state=3（二进制为0011），代表经过1号点和2号点。
state=5（二进制为0101），代表经过1号点和3号点。
state=6（二进制为0110），代表经过2号点和3号点。
…
我们设定dp[state][j]代表经过点的集合为state，并且最后一个点为j号点。
由此推出状态转移方程为：dp[state][j] = min(dp[state - (1 <<j-1) ][k] + w[k][j] )
state - (1 <<j-1)，表示从state点集中删去第j号点，w[k][j]代表从k到j路径的长度。
代表的含义为：依次遍历终点为j的每条边，以及对应的点集，从而可以推出dp[state][j]的最小值。
核心代码1：这是写的第一版代码，有个小问题
//initmemset(dp, 0x3f, sizeof dp);for (int i = 1; i <= N; i++) { //只有一个点，所以路径为0dp[1<<(i-1)][i] = 0;}//for (int state = 1; state <= (1<<N) - 1; state++) { // 枚举所有状态for (int j = 1; j <= N; j++) { // 1 or 2if(state & 1 << (j-1) && state - (1 << (j-1))){ //判断状态state是否包含第j个点，并且状态中最少有两个点。int minj = INT_MAX;for (int k = 1; k <= N; k++) {minj = min(minj, dp[state-(1<<(j-1))][k]+G[k][j]); //状态转移方程}dp[state][j] = minj;}}}
在上面的代码中的初始化部分，首先将所有状态初始化为INF,因为要求的是最小值，所有初始化为最大值，避免产生干扰。
然后将所有只有一个点的状态初始化为0.
接下来就是状态转移方程，求最小值。
但是，这里有问题，在遍历 j 的时候，我的 j 是从第一个点开始遍历的，这将导致求出来的最短路径可能不是从第一个点开始的，这样只能算出以最后一个点结尾的最短路径，而不能算出从第一个点开始，以最后一个点结尾的最短路径。
例如：
样例1：
0 10 20 999
5 0 90 30
99 50 0 10
999 1 2 0
最后求出的结果为：2 -> 1 -> 3 -> 4，明显看到不是以1号点开始。
核心代码2：改进后
//initmemset(dp, 0x3f, sizeof dp);for (int i = 1; i <= N; i++) { //只有一个点，所以路径为0dp[1<<(i-1)][i] = 0;}//for (int state = 1; state <= (1<<N) - 1; state++) { // 枚举所有状态for (int j = 2; j <= N; j++) { // 1 or 2if(state & 1 << (j-1) && state - (1 << (j-1))){ //判断状态state是否包含第j个点，并且状态中最少有两个点。int minj = INT_MAX;for (int k = 1; k <= N; k++) {minj = min(minj, dp[state-(1<<(j-1))][k]+G[k][j]); //状态转移方程}dp[state][j] = minj;}}}
改进之处为: j 不再从1号点开始，而从2号点开始，如此一来，相当于所有1号点的入边都被忽略了，只计算了1号点的出边。这样肯定只能从1号点开始。
最后附上AC代码：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <iomanip>
#include <queue>
#include <cstring>
using namespace std;typedef long long LL;typedef vector<int> vec;//#pragma GCC optimize(2)static int N;static int G[20][20];
static int dp[1<<20][20]; //dp[state][j] 经过的点集为state，最后一个点为jvoid work(void){//initmemset(dp, 0x3f, sizeof dp);for (int i = 1; i <= N; i++) { //只有一个点，所以路径为0dp[1<<(i-1)][i] = 0;}//for (int state = 1; state <= (1<<N) - 1; state++) { // 枚举所有状态for (int j = 2; j <= N; j++) { // 1 or 2if(state & 1 << (j-1) && state - (1 << (j-1))){ //判断状态state是否包含第j个点int minj = INT_MAX;for (int k = 1; k <= N; k++) {minj = min(minj, dp[state-(1<<(j-1))][k]+G[k][j]);}dp[state][j] = minj;}}}cout << dp[(1<<N)-1][N] << endl;
}int main()
{// freopen("E:\\Desktop\\data.txt", "r", stdin);//ios::sync_with_stdio(false);cin >> N;for (int i = 1; i <= N; i++) {for (int j = 1; j <= N; j++) {cin >> G[i][j];}}work();return 0;
}
