90分求助!!!
  • 板块P1433 吃奶酪
  • 楼主foryou922
  • 当前回复15
  • 已保存回复15
  • 发布时间2022/8/5 10:31
  • 上次更新2023/10/27 16:56:30
查看原帖
90分求助!!!
648393
foryou922楼主2022/8/5 10:31
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int n, a[15];
bool flag[15];
double x[15], y[15], ans = 1e9;

double cal(double x, double y, double a, double b)
{
	return sqrt((x - a) * (x - a) + (y - b) * (y - b));
}

void dfs(int step, int last, double sum)
{
	if (sum >= ans) return;
	if (step > n)
	{
		ans = min(ans,sum);
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if(flag[i]) continue;
		flag[i]=true; 
		dfs(step + 1,i,sum + cal(x[i],y[i],x[last],y[last]));
	    flag[i]=false;
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	dfs(1, 0, 0);
	cout<<fixed<<setprecision(2)<<ans<<endl;
	return 0;
}
2022/8/5 10:31
加载中...