题目大意:
给定一张 $n$ 个点的带权无向图,点从 $0∼n−1$ 标号,求起点 $0$ 到终点 $n−1$ 的最短 Hamilton 路径。
Hamilton 路径的定义是从 $0$ 到 $n−1$ 不重不漏地经过每个点恰好一次。
解题方法:
因为你看了我题解的题目所以你知道是状压DP
既然是要每个点都经过一次,首先考虑的就是状压DP,用第一维表示已经经过的点即可。
那么第二维呢?
就是当前的点啊!!!!
闫氏DP分析法上!!!
$$闫氏DP分析法$$
- 状态表示——集合:$f[i][j]$ 表示考虑所有已经经过的点经状态压缩后为 $i$(将其展开为二进制,从0开始从右往左数,是$1$就是出现过,反之亦然),且当前点为 $j$ 的最短距离
- 状态表示——属性:因为是求最短路径,故为 $min$。
- 状态计算——集合划分:考虑上一个走到的点,设上一个走到的点枚举为 $k$,则距离就是 $f[i - (1 << j)][k] + w[k][j]$。
最后还有一些判断要处理:
- 在枚举当前点时,需判断当前点是否在 $i$ 里面。
- 在循环枚举上一个点时,也需同样判断(一定要去除当前点!!!否则会出现重复的情况)
完整代码,时间复杂度:$O(2^nn^2)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 21, M = 1 << N;
int n;
int w[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 >> w[i][j];
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for (int i = 1; i < 1 << n; i ++ )
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
for (int k = 0; k < n; k ++ )
if ((i - (1 << j)) >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}