rt
题目传送门

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
const int maxn=14;
const int maxs=(1<<12)+7;
const int maxm=1e3+7;
const int inf=1e9+7;
typedef long long ll;
const ll inl=1e18;
int n,m,x,y,v,cnt;
int dis[maxn][maxn],leg[maxn][maxn];
struct edge{
	int f,t,v,nxt;
	ll cost;
	inline void set(int a,int b,int c){
		f=a;
		t=b;
		v=c;
	}
}e[maxm<<1];
int h[maxn];
ll f[maxn][maxs],ans;
int main(){
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	memset(dis,inf,sizeof(dis));
	for(int i=1;i<=n;i++)
		dis[i][i]=1;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&v);
		++cnt;
		e[cnt].set(x,y,v);
		e[cnt].nxt=h[x];
		h[x]=cnt;
		++cnt;
		e[cnt].set(y,x,v);
		e[cnt].nxt=h[y];
		h[y]=cnt;
		dis[x][y]=dis[y][x]=2;
	}
	for(int k=1;k<=n;k++)
		for(int a=1;a<=n;a++)
			for(int b=1;b<=n;b++)
				dis[a][b]=min(dis[a][b],dis[a][k]+dis[k][b]);
	int STAT=1<<n;
	ans=inl;
	memset(f,inf,sizeof(f));
	for(int x=1;x<=n;x++){
		f[x][1<<(x-1)]=f[x][0]=0;
		for(int i=1;i<=cnt;i++)
			e[i].cost=min(dis[x][e[i].f],dis[x][e[i].t])*e[i].v;
		for(int j=0;j<STAT;j++)
			for(int p=1;p<=n;p++){
				ll cst=inl;
				if(j&(1<<(p-1))){
					int S=j^(1<<(p-1));
					for(int i=h[p];i;i=e[i].nxt)
						if((1<<(e[i].t-1))&S)
							cst=min(cst,e[i].cost);
					f[x][j]=min(f[x][j],f[x][S]+cst);
				}
			}
		ans=min(ans,f[x][STAT-1]);
	}
	printf("%lld",ans);
	return 0;
}