AcWing.91,最短Hamilton路径（状态压缩dp）

本文主要是介绍AcWing.91,最短Hamilton路径（状态压缩dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一张 $n$ 个点的带权无向图，点从 0∼$n$−1 标号，求起点 0 到终点 $n$−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 $n$−1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 $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]\ge a[x,z]$。

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

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

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

使用$f[i][j]$表示：从$0$走到$j$点，中间经过的点是$i$（走过的点存到$i$里）的所有路径中的最小路径

其中$i$的每一位表示每一个点有没有走过，$1$表示走过，$0$表示没走过，如：当$i$=$1011$时，我们就走过了第$0$个点，第$1$个点,第$3$个点。（从右向左看）

如何划分情况：以倒数第二个点来分类
如果倒数第二个点为0，1，2…，$n$-1，那么当经过$k$走到$j$点时，状态将由$f[i-j,k]+a[k,j]$转移过来

代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 20, M = 1 << N;int n;
int a[N][N];
int f[M][N];int main() {cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> a[i][j];memset(f, 0x3f, sizeof f);f[1][0] = 0;	//在第0个点时为0，初始化dp数组for (int i = 0; i < 1 << n; i++)	//枚举所有状态for (int j = 0; j < n; j++)if (i >> j & 1)		//当从0走到j时，i也一定满足在j这个点位上的数为1（包含j）for (int k = 0; k < n; k++)	//枚举从哪个点转移过来if ((i - (1 << j)) >> k & 1)	//i除去j之后，一定要满足i在k这个点位上的数为1f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);	//状态转移cout << f[(1 << n) - 1][n - 1] << endl;	//走到n-1时的最短路径return 0;
}

这篇关于AcWing.91,最短Hamilton路径（状态压缩dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---