代码

#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;
int n,m;
int c[20][20],to[20][20],num[20];
int p,ans=inf; 
int tmp=0; 
int tot,cnt,vis[20],di[20];
inline bool cmp(int a,int b)
{
	return c[p][a]<c[p][b];
}
inline void dfs(int st,int sti)
{
	for(int i=st;i<=cnt;i++)
	{
		int si=vis[i];
		if(tot+tmp*di[si]>=ans)
		{
			return;
		}
		for(int j=sti;j<=num[si];j++)
		{
			int sj=to[si][j];
			if(!di[sj])
			{
				cnt++;
				vis[cnt]=sj;
				tmp-=c[sj][to[sj][1]];
				tot+=di[si]*c[si][sj];
				di[sj]=di[si]+1;
				dfs(i,j+1);
				tot-=di[si]*c[si][sj];
				di[sj]=0;
				tmp+=c[sj][to[sj][1]];
				cnt--;
			}
		}
		sti=1;
	}
	if(cnt==n)
	{
		ans=min(ans,tot);
		return;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<20;i++)
	{
		for(int j=0;j<20;j++)
		{
			c[i][j]=inf;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		if(c[u][v]<w) continue;
		if(c[u][v]==inf)
		{
			to[u][++num[u]]=v,to[v][++num[v]]=u;
		}
		c[u][v]=c[v][u]=w;
	}
	for(int i=1;i<=n;i++)
	{
		p=i;
		sort(to[i]+1,to[i]+num[i]+1,cmp);
		tmp+=c[i][to[i][1]];
	}
	//cout<<tmp;
	for(int i=1;i<=n;i++)
	{
		tot=0,cnt=1;
		vis[1]=i;
		tmp-=c[i][to[i][1]];
		di[i]=1;
		dfs(1,1);
		di[i]=0;
		tmp+=c[i][to[i][1]];
	}
	cout<<ans;
	return 0;
}

评测结果