代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,bn,a[20][20],g[1<<12][1<<12],c[1<<12][1<<12],num[1<<12],f[13][1<<12],ans=0x7fffffff;
char BuF[1<<20],*InF=BuF;
template<typename T>void read(T &x){
	for(;*InF<33;++InF);
	for(x=0;32<*InF;x=(x<<3)+(x<<1)+(*InF++^48));
}
inline int lowb(int x){
    return(x&-x);
}
int main(){
	fread(BuF,1,1<<20,stdin);
	read(n);read(m);
	bn=(1<<n)-1;
	if(n==1){
	    putchar(48);
	    return(0);
    }
	for(int i=0;i<n;++i){
		num[1<<i]=i+1;
	}
	memset(a,63,sizeof(a));
	memset(f,63,sizeof(f));
	for(int i=1,x,y,z;i<=m;++i){
		read(x);read(y);read(z);
		a[x][y]=a[y][x]=min(a[x][y],z);
	}
	for(int i=1;i<bn;++i){
		for(int j=1;j<bn;++j){
			if(!(i&j)){
				g[i][++g[i][0]]=j;
			}
		}
	}
	for(int i=1;i<bn;++i){
		for(int j=1;j<=g[i][0];++j){
			for(int k=g[i][j],tk=lowb(k);k;tk=lowb(k-=tk)){
				int mi=0xffffff;
			    for(int l=i,tl=lowb(l);l;tl=lowb(l-=tl)){
					mi=min(mi,a[num[tk]][num[tl]]);
				}
				c[i][j]+=mi;
			}
		}
	}
	for(int i=0;i<n;++i){
		f[0][1<<i]=0;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<bn;++j){
			for(int k=1;k<=g[j][0];++k){
				f[i][j|g[j][k]]=min(f[i][j|g[j][k]],f[i-1][j]+c[j][k]*i);
				if((j|g[j][k])==(1<<n)-1){
					ans=min(ans,f[i][j|g[j][k]]);
				}
			}
		}
	}
    printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return(0);
}

评测结果