[CF] 8C Looking for Order

状压模板题 CF难度2000？ 我得好好了解一下CF的难度机制了

反正CF的难度比洛谷真实就好了

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 25
#define INF 0x3f3f3f3f
using namespace std;
inline int read() {
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
	return x * f;
}
int n;
int x[N],y[N];
int g[N][N];
int f[1<<N],pre[1<<N];	//状压dp 
void print(int u) {
	printf("0 ");
	if(u == 0) return;
	int bit = u ^ pre[u];	//拿出这两个数 
	for(int i=1;i<=n;++i)
		if(bit & (1<<(i-1)))
			printf("%d ",i);
	print(pre[u]);
}
int main()
{
	x[0] = read(), y[0] = read(); n = read();
	for(int i=1;i<=n;++i)
		x[i] = read(), y[i] = read();
	memset(g, 0x3f, sizeof(g));
	for(int i=0;i<=n;++i)
		for(int j=0;j<=n;++j)
			g[i][j] = g[j][i] = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
	memset(f, 0x3f, sizeof(f));
	int maxn = (1<<n)-1;
	f[0] = 0;
	for(int S=0;S<=maxn;++S) {	//state
		if(f[S] == INF) continue;
		for(int i=1;i<=n;++i) {
			if(S & (1<<(i-1))) continue;
			for(int j=1;j<=n;++j) {
				if(S & (1<<(j-1))) continue;
				int x = S | (1<<(i-1)) | (1<<(j-1));
				int y = f[S] + g[0][i] + g[i][j] + g[j][0];
				if(y < f[x]) {
					f[x] = y;
					pre[x] = S;
				}
			}
			break;
		}
	}
	printf("%d
",f[maxn]);
	print(maxn);
	return 0;
}