Time Limit:2000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u

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  countries on the earth, which are numbered from  to . They are connected by  undirected flights, detailedly the -th flight connects the -th and the -th country, and it will cost Victor's airplane  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 , 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.

10

/*/

一开始题目没读仔细，以为是一个最小树，秒WA一发；

后来想半天发现这个有环，就不是最小树了，搜了一下是Floyd+dp状压。

写完之后一直发现输出的是INF=0x3f3f3f3f ，找了半天最后想到二进制标记状态这里，maps标记用0 0开始会舒服好多。改过来就对了。题目很有意思。。

AC代码：

/*/

#include"algorithm"

#include"iostream"

#include"cstring"

#include"cstdlib"

#include"string"

#include"cstdio"

#include"vector"

#include"cmath"

#include"queue"

using namespace std;

typedef long long LL;

#define memset(x,y) memset(x,y,sizeof(x))

#define memcpy(x,y) memcpy(x,y,sizeof(x))

#define MX 401

#define INF 0x3f3f3f3f

int maps[20][20];

int dp[200000][20],vis[20];

void init() {

	memset(maps,0x3f);

	memset(vis,0x3f);

	memset(dp ,0x3f);

}

int main() {

	int T;

	scanf("%d",&T);

	while(T--) {

		init();

		int n,m,u,v,w;

		scanf("%d%d",&n,&m);

		for(int i=0; i<m; i++) {

			scanf("%d%d%d",&u,&v,&w);

			if(maps[--u][--v] > w)    //状态压缩从0开始会好写一些

				maps[v][u]=maps[u][v]= w;

		}

		for(int i=0; i<n; i++)maps[i][i]=0; //标记自己到自己距离为0   //后面会要加到这个数字。。

		for(int k=0; k<n; k++) {

			for(int i=0; i<n; i++) {

				for(int j=0; j<n; j++) {

					maps[i][j]=min(maps[i][j],maps[i][k]+maps[k][j]); //Floyd 把去某一点的最小路程计算出来

				}

			}

		}

		dp[1][0]=0;

		vis[0]=0;

		m=1<<n;

		for(int i=1; i<m; i++) {

			for(int j=0; j<n; j++) {

				if(dp[i][j]==INF)continue;

				for(int k=0; k<n; k++) {

					if(i&(1<<k)||maps[j][k]==INF)continue;  //二进制 1 表示该点走过，0表示没走过，第二维表示现在所在的点。压缩状态

					if( dp[i|(1<<k)][k]>dp[i][j]+maps[j][k]) {

						dp[i|(1<<k)][k]=dp[i][j]+maps[j][k];

						vis[k]=min(vis[k],dp[i|(1<<k)][k]); //比较，去到下一点需要的最小路

					}

				}

			}

		}

		int minn=1e9+100;;

		for(int i=0; i<n; i++) {

			minn=min(minn,dp[m-1][i]+vis[i]);

		}

		printf("%d\n",minn);

	}

	return 0;

}