55pts

#include<bits/stdc++.h>
using namespace std;
int n,m,sz[15][15]={0},f[4097],dis[15][4097],ans=INT_MAX;
int anw(int x,int l){
	return ((x>>l)&1);
}
int main(){
//	freopen("24,out","w",stdout);
	cin>>n>>m;
	memset(f,0x3f,sizeof(f));
	int u,v,w;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		if(!sz[u][v])	sz[u][v]=sz[v][u]=w;
		else	sz[u][v]=sz[v][u]=min(sz[u][v],w);
	}	
	for(int s=1;s<=n;s++){
		memset(f,0x3f,sizeof(f)),memset(dis,0,sizeof(dis));
		f[(1<<n-s)]=0;
		for(int i=1;i<=(1<<n)-1;i++){
			if(!anw(i,n-s)||i==(1<<n-s))	continue;
			for(int j=1;j<=n;j++){
				if(!anw(i,n-j)||j==s)	continue;
				int t=i-(1<<n-j);//上一个状态 cout<<"!";
//				if(s==1)	cout<<i<<" "<<t<<'\n';
				for(int k=1;k<=n;k++){
					if(j==k||!anw(t,n-k)||!sz[j][k])	continue;
					if(f[t]+dis[k][t]*sz[j][k]<f[i]){
						f[i]=f[t]+(dis[k][t]+1)*sz[j][k];
						dis[j][i]=dis[k][t]+1;
						for(int l=1;l<=n;l++){
							if(l!=j)	dis[l][i]=dis[l][t];
						}
					}
				}
			}
		}
		ans=min(ans,f[(1<<n)-1]);
	}
	cout<<ans;
	return 0;
}

可悬关，thx