搜索求助,我就想拿个70分,但是只能拿到30
  • 板块P1433 吃奶酪
  • 楼主n_bluetea
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/3/30 09:42
  • 上次更新2023/10/23 20:03:35
查看原帖
搜索求助,我就想拿个70分,但是只能拿到30
588080
n_bluetea楼主2023/3/30 09:42
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

int n;
double sum;
double ans = 900000000.0;

int v[10000];
double dis[100][100];

struct node
{
	double x;
	double y;
}box[10000];

double length(double x1,double y1,double x2,double y2)
{
	return 	sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

void dfs(int step)
{
	if(sum>ans)
		return; 
	
	if(step == n)
	{
		ans = min(ans,sum);
		return;
	}
		
	for(int i=1;i<=n;i++)
	{
		if(i==step || v[i])
			continue; 
		
		v[i] = 1;
		sum += dis[step][i];
		
		dfs(step+1);
		
		v[i] = 0;
		sum -= dis[step][i];
	} 
}

int main()
{
	
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		cin>>box[i].x;
		cin>>box[i].y;
	}
	
	box[0].x=0;
	box[0].y=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			dis[i][j] = length(box[i].x , box[i].y , box[j].x , box[j].y);
		}
	}
	
	dfs(0);
	printf("%.2lf",ans);
	return 0;
}
2023/3/30 09:42
加载中...