hdu5418 floyed 旅行商问题

hdu5418 Victor and World
传送门
有一个n个顶点，m条边的图，每条边都有正权值，从1号点出发，经过每个顶点至少一次，最后回到1号点，求总权值的最小值。
1<=n<=16，1<=m<=100000。

每个顶点可以重复经过，首先利用floyed计算出两个顶点之间的最短距离，变成旅行商问题，然后使用状压dp来求解。
顶点编号变为[0,n-1]。
使用二进制来表示顶点集合，已经访问过的顶点集合为S，当前所在的顶点为v，dp[S][v]表示从v出发访问剩余的所有顶点，最后回到0号点的总权值的最小值。V表示所有顶点的集合，递推式：

使用记忆化搜索推出矩阵dp。
对于每一种状态，遍历当前所在的顶点和转移过来的顶点，时间复杂度为\(O({2^n}{n^2})\)。

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define pi acos(-1.0)
#define lowbit(x) x&(-x)
using namespace std;

const int maxn=16;
int T,n,m,w[20][20],dp[1<<maxn][maxn];

int f(int S,int v){
	if(dp[S][v]!=-1) return dp[S][v];
	int res=INT_MAX;
	for(int u=0;u<n;u++){
		if(!((S>>u) & 1)) res=min(res,f(S|(1<<u),u)+w[v][u]);
	}
	return dp[S][v]=res;
}

int main(void){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);
		memset(w,0x3f,sizeof(w));
		for(int i=0;i<n;i++) w[i][i]=0;
		while(m--){
			int u,v,ww;
			scanf("%d %d %d",&u,&v,&ww);
			u--;
			v--;
			w[u][v]=min(w[u][v],ww);
			w[v][u]=w[u][v];
		}
		for(int k=0;k<n;k++){
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(w[i][j]>w[i][k]+w[k][j]) w[i][j]=w[i][k]+w[k][j];
				}
			}
		}
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<n;i++) dp[(1<<n)-1][i]=w[0][i];
		printf("%d\n",f(0,0));
	}
	return 0;
}

hdu5418 floyed 旅行商问题

原文：https://www.cnblogs.com/fxq1304/p/13131089.html