记录编号	477299	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017]宝藏	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.983 s
提交时间	2017-12-02 11:48:30	内存使用	129.46 MiB

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;	
}
const int maxn=25,SIZEN=1<<12,INF=0x3f3f3f3f;
int n,m,dis[maxn][maxn],d[maxn][SIZEN];
long long f[maxn][SIZEN],ans=1ll<<62,g[SIZEN][SIZEN];
void Min(int &x,int y){if(x>y)x=y;}
void Min(long long &x,long long y){if(x>y)x=y;}
int main(){
	freopen("2017treasure.in","r",stdin);freopen("2017treasure.out","w",stdout);
	R_int(n),R_int(m);int i,j,v,a,b,c,S=1<<n;
	if(n==1){puts("0");return 0;}
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i^j)dis[i][j]=INF;
	while(m--)R_int(a),R_int(b),R_int(c),Min(dis[a][b],c),dis[b][a]=dis[a][b];
	for(i=1;i<=n;i++)
	for(v=1;v<S;v++)if(!(v>>(i-1)&1))
		for(d[i][v]=INF,j=0;j<n;j++)
			if(v>>j&1)Min(d[i][v],dis[i][j+1]);
	for(v=1;v<S;v++)
	for(j=(v-1)&v;j;j=(j-1)&v)
	for(i=0;i<n;i++)
		if(j>>i&1)g[v][j]+=d[i+1][v^j];
	for(v=0;v<S;v++)f[0][v]=1ll<<60;
	for(i=0;i<n;i++)f[0][1<<i]=0;
	for(i=1;i<n;i++){
		for(v=1;v<S;v++)
			for(f[i][v]=1ll<<60,j=(v-1)&v;j;j=(j-1)&v)
				Min(f[i][v],f[i-1][v^j]+g[v][j]*1ll*i);
		Min(ans,f[i][S-1]);
	}
	printf("%lld\n",ans);
}