代码

#include<bits/stdc++.h>
using namespace std;

int n,m,val[12][12],ans,bestn[12],best,ii,mindp[12],bestnn[12];
int to[12][13];//数量，12*边。 

struct node{
	int w,dp[12],expect;//dp[i][j]点i深度为j 
}f[65536];

void find(int k)
{
	if(k==(1<<n)-1)
	{
		//printf("#%d&%d\n",f[k].w,best);
		ans=min(f[k].w,ans);
		return;
	}
	if(f[k].w+best>=ans)return;
	int mk,j;
	for(int i=0;i<n;i++)
	{
		if(!(k&(1<<i)))continue;
		for(int jj=1;jj<=to[i][0];jj++)
		{
			j=to[i][jj];
			if(k&(1<<j))continue;
			mk=k|(1<<j);
			memcpy(f[mk].dp,f[k].dp,sizeof(f[k].dp));
			f[mk].w=f[k].w+f[k].dp[i]*val[i][j];
			f[mk].dp[j]=f[k].dp[i]+1;
			best-=bestn[j];
			find(mk);
			best+=bestn[j]; 
		}
	}
}

void solve(int rt)
{
	memset(f,0,sizeof(f));
	memset(mindp,0,sizeof(mindp));
	f[1<<rt].w=0;
	f[1<<rt].dp[rt]=1;
	
	best=0;
	mindp[rt]=1;
	queue<int>q;
	q.push(rt);
	int p;
	while(!q.empty())
	{
		p=q.front();q.pop();
		for(int i=1;i<=to[p][0];i++)
		{
			if(mindp[to[p][i]])continue;
			mindp[to[p][i]]=mindp[p]+1;
			bestn[to[p][i]]=mindp[to[p][i]]*bestnn[to[p][i]];
			best+=bestn[to[p][i]];
			q.push(to[p][i]);
		}
	}
	find(1<<rt);
}

bool cmp(int a,int b)
{
	return val[ii][a]<val[ii][b];
}

int main()
{
	//freopen("test.in","r",stdin);
	int m1,m2,m3;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)val[i][j]=0x7fffffff;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&m1,&m2,&m3);
		m1--;m2--;
		val[m1][m2]=min(val[m1][m2],m3);
		val[m2][m1]=min(val[m2][m1],m3);	
	}
	for(int i=0;i<n;i++)
	{
		m1=0;
		for(int j=0;j<n;j++)
		{
			if(val[i][j]==0x7fffffff)continue;
			to[i][++m1]=j;
		}
		to[i][0]=m1;
		ii=i;
		sort(to[i]+1,to[i]+1+m1,cmp);
		bestnn[i]=val[i][to[i][1]];
	}
	ans=0x7fffffff;
	for(int i=0;i<n;i++)solve(i);
	cout<<ans;
}

评测结果