【HDU - 5418】Victor and World（tsp旅行商问题，状压dp，floyd最短路，图论）

题干：

After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are nn countries on the earth, which are numbered from 11 to nn. They are connected by mm undirected flights, detailedly the ii-th flight connects the uiui-th and the vivi-th country, and it will cost Victor's airplane wiwi L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country. 

Victor now is at the country whose number is 11, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country.

Input

The first line of the input contains an integer TT, denoting the number of test cases. 
In every test case, there are two integers nn and mm in the first line, denoting the number of the countries and the number of the flights. 

Then there are mm lines, each line contains three integers uiui, vivi and wiwi, describing a flight. 

1≤T≤201≤T≤20. 

1≤n≤161≤n≤16. 

1≤m≤1000001≤m≤100000. 

1≤wi≤1001≤wi≤100. 

1≤ui,vi≤n1≤ui,vi≤n.

Output

Your program should print TT lines : the ii-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.

Sample Input

1
3 2
1 2 2
1 3 3

Sample Output

10

题目大意：

有n个城市，在n个城市之间有m条双向路，每条路有一个距离，现在问从1号城市出发，去游览其它的2到n号城市最后回到1号城市的最短路径（题目数据保证1可以直接或间接到达其他城市）。（n<=16）

解题报告：

因为每个点可以走多次所以不是哈密顿回路，这一个特性也就决定了我们可以用floyd求最短路。

dp[sta][v]代表走过状态为sta并且当前站在v这个城市的最小距离。最后加一个回到原点的距离就行了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int n,m;
int head[MAX],tot;
int dis[22][22];
int dp[1<<18][18];
bool ok[22];
struct Edge {
	int fr,to,ne;
	int w;
} e[MAX];
void add(int u,int v,int w) {
	e[++tot].fr = u;
	e[tot].to = v;
	e[tot].w = w;
	e[tot].ne = head[u];
	head[u] = tot;
}
void floyd() {
	for(int k = 0; k<n; k++) {
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
			}
		}
	}
}
int tsp() {
	int up = 1<<n;
	dp[1][0] = 0; 
	for(int sta = 0; sta < up; sta++) {
		memset(ok,0,sizeof ok);
		for(int i = 0; i<n; i++) {
			if((1<<i) & sta) ok[i] = 1;
		}
		for(int u = 0; u<n; u++) {			
			//可以if(dp==-1)continue  也可以先初始化成0x3f3f3f3f？？？ 
			for(int v = 0; v<n; v++) {
				if(ok[v]) continue;
				dp[sta|(1<<v)][v] = min(dp[sta|(1<<v)][v],dp[sta][u] + dis[u][v]);
			}
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 0; i<n; i++) {
		ans = min(ans,dp[up-1][i] + dis[i][0]);
	}
	return ans;
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d",&n,&m);
		//init 
		tot=0;
		memset(dis,0x3f,sizeof dis);
		memset(dp,0x3f,sizeof dp);
		for(int i = 0; i<n; i++) head[i] = -1,dis[i][i] = 0;
		for(int u,v,w,i = 1; i<=m; i++) {
			scanf("%d%d%d",&u,&v,&w);
			u--,v--;
			add(u,v,w);add(v,u,w);
			if(w < dis[u][v]) dis[u][v] = dis[v][u] = w;
		}
		floyd();
		cout << tsp() << endl;
	}
	return 0 ;
}