P1433 吃奶酪

WA+TLE+AC 10分求助

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
struct node {
	int id;
	double x, y;
} a[maxn];
int n, p[maxn];
double ans = 1e9, d[maxn][20];
int lowbit(int x) {
	return x & -x;
}
double dist(node a, node b) {
	return sqrt((a.x - b.x) * (a.x - b.x) - (a.y - b.y) * (a.y - b.y));
}
void dfs(int step, int v, double sum, node pre) {
	if (step == n + 1) {
		ans = min(ans, sum);
		return ;
	}
	if (sum >= ans || d[v][pre.id] < sum && d[v][pre.id] > 0) return ;
	d[v][pre.id] = sum;
	int t = v, lt;
	while (t) {
		lt = lowbit(t);
		t -= lt;
		dfs(step + 1, v - lt, sum + dist(pre, a[p[lt]]), a[p[lt]]);
	}
	return ;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < 16; i++) p[1 << i] = i + 1;
	for (int i = 1; i <= n; i++) {
		scanf("%lf %lf", &a[i].x, &a[i].y);
		a[i].id = i;
	}
	dfs(1, (1 << n) - 1, 0, node{0, 0});
	printf("%.2lf", ans);
	return 0;
}