心态崩了呀--萌新求助
查看原帖
心态崩了呀--萌新求助
233957
190040257a楼主2020/5/25 18:01

就按着状压基本思路做的,其他几个点都没问题,就两个点玄学RE还有一个点WA,找问题找了很久也没找到。。求大佬告知问题在哪

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
double suan[20][40000];
double x[20];
double y[20];
bool sf[40];
int N;
double qh(int xx,int yy)
{
	double x1=x[xx];
	double x2=x[yy];
	double y1=y[xx];
	double y2=y[yy];
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
	cin>>N;
	memset(suan,127,sizeof(suan));
	for(int i=1;i<=N;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
	}
	for(int l=1;l<=(1<<N)-1;l++)
	{
		for(int i=1;i<=N;i++)
		{
			if(l&(1<<(i-1))==0)continue;
			if(l==(1<<(i-1)))
			{
				suan[i][l]=0;
				continue;
			}
			for(int j=1;j<=N;j++)
			{
				for(int j=1;j<=N;j++)
				{
					if(i==j||l&(1<<(j-1))==0)continue;
					suan[i][l]=min(suan[i][l],suan[j][l-(1<<(i-1))]+qh(i,j));
				}
			}
		}
	}
	double maxn=1e9;
	for(int i=1;i<=N;i++)
	{
		maxn=min(maxn,suan[i][(1<<N)-1]+qh(i,0));
	}
	printf("%.2lf\n",maxn);
	return 0;
}

2020/5/25 18:01
加载中...