代码

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

int n,m,val[12][12],ans;

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

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

void solve(int rt)
{
	memset(f,0,sizeof(f));
	f[1<<rt].w=0;
	f[1<<rt].dp[rt]=1;
	find(1<<rt);
}

int main()
{
	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);	
	}
	ans=0x7fffffff;
	for(int i=0;i<n;i++)solve(i);
	cout<<ans;
}

评测结果