关于 O(n^2 * 2^n) 第 9 个点冲不过去

// 2023 Spring Test T3 tree
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
const double eps = 1e-10;
int n, k;
double x[N], y[N], dp[N][1 << N], pre[N][1 << N];
double dis (int i, int j) {
	return sqrt (pow (x[i] - x[j], 2) + pow (y[i] - y[j], 2));
}
int lowbit (int x) {
	return x & (-x);
}
int lowpls (int x) {
	int y = lowbit (x);
	switch (y) {
		case 1: return 1;
		case 2: return 2;
		case 4: return 3;
		case 8: return 4;
		case 16: return 5;
		case 32: return 6;
		case 64: return 7;
		case 128: return 8;
		case 256: return 9;
		case 512: return 10;
		case 1024: return 11;
		case 2048: return 12;
		case 4096: return 13;
		case 8192: return 14;
		case 16384: return 15;
		case 32768: return 16;
		case 65536: return 17;
		case 131072: return 18;
		default: return -1;
	}
}
double dfs (int e, int S) {
	if (abs (dp[e][S] + 1.0) > eps) {
		return dp[e][S];
	}
	int kkk = S;
	double ans = 1e20;
	int in = 0;
	vector <int> vis;
	while (kkk != 0) {
		int i = lowpls (kkk);
		kkk -= lowbit (kkk);
		vis.push_back (i);
	}
	for (auto i : vis) {
		if (i == e) {
			continue;
		}
		double cans = dfs (i, S - (1 << e - 1)) + dis (i, e);
		if (cans < ans) {
			in = i;
			ans = cans;
		}
	}
	pre[e][S] = in;
	return dp[e][S] = ans;
}
void print (int e, int S) {
	if (S == 0) {
		return;
	}
	print (pre[e][S], S - (1 << e - 1));
	printf ("%d%c", e, " \n"[S == (1 << n) - 1]);
}
int main () {
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf ("%lf%lf", &x[i], &y[i]);
		if (i == 1 || y[i] > y[k]) {
			k = i;
		}
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 0; i < (1 << n); i++) {
			dp[j][i] = -1.0;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i == k) {
			dp[i][1 << i - 1] = 1.0;
		} else {
			dp[i][1 << i - 1] = 1e20;
		}
	}
	int e = 0;
	double ans = 1e20;
	for (int i = 1; i <= n; i++) {
		double cans = dfs (i, (1 << n) - 1);
		if (cans < ans) {
			e = i;
			ans = cans;
		}
	}
	print (e, (1 << n) - 1);
	return 0;
}