AcWing算法基础课笔记——最短Hamilton路径

最短Hamilton路径

题目

给定一张 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
输入样例：
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 = 111000，表示走过前面3个点到j的路径。

因此f[i, j]可以由路径的倒数第二个节点划分，也就是说可以根据倒数第二个节点是0 ，1， 2， …，n - 1来划分f[i, j]的来源。

若有一条从0 - > … - > k - > j的路径，k是f[i, j]的倒数第二个结点，那么f[i, j] = f[i - {j}, k] + a[k, j]。其中i - {j}表示在i中删去j这个结点，a[k, j]表示从k走到j的代价。

代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 20, 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; // 从0走到0的路径代价为0
	
	//列举所有路径i
	for(int i = 0; i < 1 << n; i ++ ) {
		//列举所有结点 j
		for(int j = 0; j < n; j ++ ) {
			// 如果i 包含了j 
			if(i >> j & 1) {
				//列举路径i上除了j的其他点k  
				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]); 
					}
				} 
			}
		}
	} 
	
	//答案为走过所有路径的到n - 1的路径的代价 
	cout << f[(1 << n) - 1][n - 1] << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43