萌新求助,最后一个点TLE
  • 板块P1433 吃奶酪
  • 楼主HMP_Haoge
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/7/4 23:06
  • 上次更新2023/11/6 23:38:52
查看原帖
萌新求助,最后一个点TLE
254036
HMP_Haoge楼主2020/7/4 23:06

相当丑陋的代码,还望谅解

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
#define ri register int 

int n;
double ans[17][17];
struct NoDe{
	double x;
	double y;
}arr[17];
bool brr[17];
double mini=10000.0;

inline double Dist(NoDe i,NoDe j)
{
	return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}

inline void search(int poi,double cur,int k)
{
	if(cur>mini)
	{
		return;
	}
	if(k==n)
	{
		if(cur<mini)
		{
			mini=cur;
		}
		return;
	}
	for(ri i=1;i<=n;i++)
	{
		if(brr[i]==0)
		{
			brr[i]=1;
			search(i,cur+ans[poi][i],k+1);
			brr[i]=0;
		}
	}
}


int main()
{
//	freopen("card.in","r",stdin);
//	freopen("card.out","w",stdout);
	scanf("%d",&n);
	for(ri i=1;i<=n;i++)
		scanf("%lf %lf",&arr[i].x,&arr[i].y);
	n++;
	arr[n].x=0.0;
	arr[n].y=0.0;
	for(ri i=1;i<=n;i++)
		for(ri j=i+1;j<=n;j++)
		{
			ans[i][j]=Dist(arr[i],arr[j]);
			ans[j][i]=ans[i][j];
		}
	n--; 
	search(n+1,0,0);
	printf("%.2lf\n",mini);
	return 0;
}
2020/7/4 23:06
加载中...