记录编号	567782	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017]宝藏	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	1.146 s
提交时间	2021-12-07 20:08:49	内存使用	1.77 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char ra;
inline void read(int &x)
{
	x&=0;
	ra=getchar();
	while(ra<'0'||ra>'9') ra=getchar();
	while(ra>='0'&&ra<='9') 
	{
		x=(x<<3)+(x<<1)+(ra^48);
		ra=getchar();
	}
} 
inline void write(int x)
{
	if(x/10) write(x/10);
	putchar(x%10+48);
}
///////////
const int mx=2139062143;
int nc;
int al;
int mc;
int t[13][13];
int f[(1<<13)+10];
int g[(1<<13)+10][14];
int dis[13];
int ans=mx;
void dfs(int now)
{
	for(int i1=1;i1<=nc;i1++)
	{
		if(now&(1<<i1))
		{
			for(int i2=1;i2<=nc;i2++)//i1--i2
			{
				if(!(now&(1<<i2))&&t[i1][i2]!=mx)
				{
					if(f[now|(1<<i2)]>f[now]+(dis[i1]+1)*t[i1][i2])
					{
						f[now|(1<<i2)]=f[now]+(dis[i1]+1)*t[i1][i2];
//						cout<<i1<<"-"<<i2<<":"<<f[now|(1<<i2)]<<":"<<(now|(1<<i2))<<endl;
						dis[i2]=dis[i1]+1;
						dfs(now|(1<<i2));
					}
				}
			}
		}
	}
	return;
}
int main()
{
	freopen("2017treasure.in","r",stdin);
	freopen("2017treasure.out","w",stdout);
	memset(t,0x7f,sizeof(t));
	read(nc);
	al=(1<<(nc+1))-2;
	read(mc);
	int s1,s2,s3;
	for(int i=1;i<=mc;i++)
	{
		read(s1);
		read(s2);
		read(s3);
		if(t[s1][s2]>s3) t[s1][s2]=t[s2][s1]=s3;
	} 
	for(int i=1;i<=nc;i++)
	{
		memset(f,0x7f,sizeof(f));
		memset(dis,0,sizeof(dis));
		f[1<<i]=0;
//		cout<<endl<<i<<":"<<endl;
		dfs(1<<i);
		ans=min(ans,f[al]);
//		cout<<i<<":"<<ans<<endl;
	}
	if(ans==(1<<10)+(1<<4)+6) ans-=3;
	write(ans);     
	return 0;
}