题意：本题要求一棵生成树，并使求出的生成树为满足题目要求（sum(路径长度*经过的节点数)）的最小值

解法：状压DP+DFS

1.对于树的节点的状态用普通的 vis数组难以表示，所以就用到了状态压缩，可以非常简单明了的表示出已搜索过的树的状态，以便于统计答案；同时可以看到，题目的 n只有 12

注意！！题目可能会有重边

附上代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int N = 21;
const int inf = 2147483647;

int n,m,ans=inf;
int w[N][N],f[100086],sum[N];

void ljw(int x){
	for(int i=1;i<=n;i++){
		if((1<<(i-1))&x){
			for(int j=1;j<=n;j++){
				if(((1<<(j-1))&x)==0&&w[i][j]!=inf){
					if(f[x|(1<<(j-1))]>f[x]+sum[i]*w[i][j]){
						int temp=sum[j];
						sum[j]=sum[i]+1;
						f[x|(1<<(j-1))]=f[x]+sum[i]*w[i][j];
						ljw(x|(1<<(j-1)));
						sum[j]=temp;
					}
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++) w[i][j]=inf;
	for(int i=1;i<=m;i++){
		int u,v,z;
		scanf("%d%d%d",&u,&v,&z);
		w[u][v]=min(w[u][v],z);
		w[v][u]=min(w[v][u],z);//边可能会有重复 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) sum[j]=inf;
		for(int j=1;j<=(1<<n)-1;j++) f[j]=inf;
		sum[i]=1;
		f[1<<(i-1)]=0;
		ljw(1<<(i-1));
		ans=min(ans,f[(1<<n)-1]);
	}
	printf("%d",ans);
	return 0;
}