求助!!!标准dfs70分
  • 板块P1433 吃奶酪
  • 楼主_Aurore_
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/3/22 18:07
  • 上次更新2023/10/28 05:56:08
查看原帖
求助!!!标准dfs70分
593595
_Aurore_楼主2022/3/22 18:07
#include<bits/stdc++.h>
using namespace std;
struct cheese{
	double x,y;
}c[110];
double sum=0;
bool use[110];
int input;
double ans=1000000000;
void dfs(int cen,int x_now,int y_now){
	if(cen>input){
		ans=min(ans,sum);
		return ;
	}
	if(sum>ans)  return;
	for(int i=1;i<=input;i++){
		if(use[i]==true){
			use[i]=false;
			sum+=sqrt((x_now-c[i].x)*(x_now-c[i].x)+(y_now-c[i].y)*(y_now-c[i].y));
			dfs(cen+1,c[i].x,c[i].y);
			sum-=sqrt((x_now-c[i].x)*(x_now-c[i].x)+(y_now-c[i].y)*(y_now-c[i].y));
			use[i]=true;
		}
	}
}
int main(){
	cin>>input;
	for(int i=1;i<=input;i++){
		cin>>c[i].x>>c[i].y;
		use[i]=true;
	}
	//use[1]=false;
	dfs(1,0,0);
	printf("%.2lf",ans);
}
2022/3/22 18:07
加载中...