原题 P3959

死因：这份代码开 O2 会固定 WA 50 分，关 O2 会 TLE，实测后者 TLE 的原因是单纯跑的慢。

#include <iostream>
#include <stdio.h>
using namespace std;
int inf=2147483647;
int cost[1<<13][1<<13];
int dp[15][1<<13];
int a[15][15],n,m;
void init(){
	for(int i=1;i<(1<<n);++i) for(int j=i;j;j=(j-1)&i){
		if(i==j) continue;
		for(int u=0,r;u<n;u++,r=inf){
			if(!(((i^j)>>u)&1))continue;
			for(int v=0;v<n;v++)
				if((j>>v)&1) r=min(r,a[u][v]);
			if(r>=inf){cost[j][i]=inf;break;}
			else cost[j][i]+=r;
		}
	}
}
int DP(int x){
	for(int i=0;i<=n;++i) for(int j=0;j<(1<<n);++j) dp[i][j]=inf;
	dp[0][1<<x]=0;
	int res=inf;
	for(int c=1;c<n;++c)
		for(int i=1;i<(1<<n);++i){
			for(int j=i;j;j=(j-1)&i){
				if(i==j) continue;
				dp[c][i]=min((long long)dp[c][i],(long long)dp[c-1][j]+1ll*c*(long long)cost[j][i]);
			}
			if(i==(1<<n)-1) res=min(res,dp[c][i]); 
		}
	return res;
}
signed main(){
	scanf("%d%d",&n,&m);
	if(n==1) {printf("0\n");return 0;}
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) a[i][j]=inf;
	for(int i=1;i<=m;++i){
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		--u,--v;
		a[u][v]=a[v][u]=min(a[u][v],w);
	}
	init();
	int res=inf;
	for(int i=0;i<n;++i) res=min(res,DP(i));
	printf("%d\n",res);
}