提炼
首先看到24
那无疑是状态压缩
这样我们dp[1<<24]就是 收集到state状态的min
关于转移 我们需要枚举当前状态下的两个0位 复杂度显然是2424（1<<24）级别的 虽然有剪枝
但是 我们仔细一想 我们的答案 不需要 任何的顺序 证明我们可以随便拿出最优的一组即可
我们找到第一个0位 这个位置显然要和其他配对 并且肯定有最优的一组
然后我们break即可 这样复杂度就是24*（1《24）
int dp[1<<24],pre[1<<24];
int dis[25][25];
int dist(PII A,PII B){return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);}
void solve() {
PII C;
cin >> C.first >> C.second;
int n;
cin >> n;
vector<PII > a(n + 1);
a[n] = C;
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dis[i][j] = dist(a[i], a[j]);
}
}
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 0 ; i < (1<<n); i++) {
if (dp[i] == 0x3f3f3f3f)continue;
for (int j = 0; j < n; j++) {
if (i >> j & 1)continue;
for (int k = j; k < n; k++) {
if (i >> k & 1)continue;
int w = dis[j][k] + dis[j][n] + dis[n][k];
if (dp[i | (1 << j) | (1 << k)] > dp[i] + w) {
dp[i | (1 << j) | (1 << k)] = dp[i] + w;
pre[i | (1 << j) | (1 << k)] = i;
}
}
break; //zhongdian
}
}
cout << dp[(1 << n) - 1] << endl;
int y = (1 << n) - 1;
vector<int> ans;
while (y) {
auto ny = pre[y];
ans.push_back(0);
for (int i = 0; i < n; i++) {
if (!(ny >> i & 1) && (y >> i & 1)) {
ans.push_back(i + 1);
}
}
y = ny;
}
ans.push_back(0);
reverse(all(ans));
for (auto i: ans)cout << i << ' ';
}