Why?爆搜为啥会TLE?90分
查看原帖
Why?爆搜为啥会TLE?90分
798157
emo_male_god楼主2023/4/12 20:25

样例十: 15 0 0 1 1 1 -1 -1 1 -1 -1 2 2 2 0 2 -2 0 -2 -2 -2 -2 0 -2 2 0 2 1 3 1 4 代码:

#include <iostream>
#include <cmath>

using namespace std;

const int N = 20;
struct node
{
	double x, y;
}a[N];
int n;
bool b[N];
double ans = 123456.0;

void dfs(double xx, double yy, int xnt, double temp)
{
	if (xnt == n)
	{
		ans = min(ans, temp);
		return;
	}
	if (temp >= ans) return;
	for (int i = 1; i <= n; i ++ )
	{
		if (b[i] == false)
		{
			b[i] = true;
			dfs(a[i].x, a[i].y, xnt + 1, temp + sqrt((a[i].x - xx) * (a[i].x - xx) + (a[i].y - yy) * (a[i].y - yy)));
			b[i] = false;
		}
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &a[i].x, &a[i].y);
//	for (int i = 1; i <= n; i ++ ) printf("%lf %lf\n", a[i].x, a[i].y);
	dfs(0, 0, 0, 0);
	printf("%.2lf\n", ans);
	return 0;
}
2023/4/12 20:25
加载中...