最短Hamilton路径

时间限制: 4 Sec 内存限制: 128 MB

题目描述

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

输入

第一行一个整数n。

接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（一个不超过10^7的正整数，记为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路径的长度。

样例输入

样例输出

已AC代码

#define LL long long
#include <bits/stdc++.h>
using namespace std;
int w[21][21];
int dp[21][(1 << 20)+5];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) cin >> w[i][j];
	memset(dp,0x3f,sizeof(dp));
	dp[0][1] = 0;
	for(int i=1;i<(1 << n);++i){
		for(int j=0;j<n;++j){
			if((1 << j) & i){
				for(int k=0;k<n;k++){
					if(j == k) continue;
					if((1 << k) & i){
						dp[j][i] = min(dp[j][i],dp[k][(1 << j) ^ i] + w[k][j]);
					}
				}
			}
		}
	}
	cout << dp[n-1][(1 << n) - 1];
	
	return 0;
}

思想

1、记录两个状态：经过了哪些点，现在在那个点上。

2、用动态规划——状态压缩，用二进制数记录状态。

例如：有四个点A，B，C，D，0101是数5，代表着经历了A点和C点。

3、用位运算：判断和筛选正确的经历状态。

4、进行最小值刷新。

注意点

1、#include <bits/stdc++.h>

尽量少用，因为引入的头文件太多，影响编译速度，在打比赛时，会拖节奏

2、int dp[21][(1 << 20)+5];

1<<21太大，会超限

3、memset(dp,0x3f,sizeof(dp));

0x代表该数是16进制，0x3f默认补成0x3f3f3f3f，接近int型最大值的一半

4、if((1 << j) & i)

此语句用来判断是否到过j点，如果没到过，则不是合法的数据，不用赋值

5、if((1 << k) & i)

此语句用来判断是否到过k点，如果到过，则刷新最小路径值

6、dp[j][i] = min(dp[j][i],dp[k][i-(1<<j)] + w[k][j]);

dp[k][(1 << j) ^ i] = dp[k][i-(1<<j)] 表示此时在k点,经历了j点之前的所有点的最小路径值

7、cout << dp[n-1][(1 << n) – 1];

dp[n-1][(1 << n) – 1] 表示此时在n-1点上，经历了n-1及之前所有的点的最小路径值