捞
查看原帖
捞
733118
Won_DER楼主2024/1/18 18:56

大佬们求调代码,实在不行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() cout<<"LSY"<<endl;
typedef unsigned long long ull;
const int N=15;
const int M=1<<15;
const int INF=0x3f3f3f3f;//const int INF=1e9;
const double eps=1e-8;
const int mod=1e9+7;
int n,m;
int g[M],d[N][N];
int dp[M][N];

signed main()
{
	cin>>n>>m;
	memset(d,0x3f,sizeof(d));
	for(int i=0;i<n;++i) d[i][i]=0;
	for(int i=1;i<=m;++i)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		d[a][b]=d[b][a]=min(d[a][b],c);
	}
	for(int i=0;i<(i<<n);++i)
		for(int j=0;j<n;++j)
			if(i>>j&1)
			{
				for(int k=0;k<n;++k)
					if(d[j][k]!=INF) 
						g[i]|=1<<k;
			}
	memset(dp,0x3f,sizeof(dp));
	for(int i=0;i<n;++i) dp[1<<i][0]=0;
	for(int i=0;i<(1<<n);++i)
	{
		for(int j=i;j;j=(j-1)&i)
		{
			if((g[j]&i)==i)
			{
				int temp=i^j;
				int cost=0;
				for(int k=0;k<n;++k)
				{
					if(temp>>k&1)
					{
						int t=INF;
						for(int q=0;q<n;++q)
							if(j>>q&1) t=min(t,d[k][q]);
						cost+=t;
					}
				}
				for(int k=1;k<n;++k) dp[i][k]=min(dp[i][k],dp[j][k-1]+cost*k);
			}
		}
	}
	int ans=INF;
	for(int i=0;i<n;++i) ans=min(ans,dp[(1<<n)-1][i]);
	cout<<ans<<endl;
//	cout<<dp[(1<<n)-1][n]<<endl;
	return 0;
}
2024/1/18 18:56
加载中...