比赛 SYOI2022 Round2 评测结果 AAATTTTTAA
题目名称 Looking for Order 最终得分 50
用户昵称 op_组撒头屯 运行时间 27.929 s
代码语言 C++ 内存使用 4.01 MiB
提交时间 2022-06-15 20:09:33
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=24+3;
const int inf=0x7fffffff;
bool ok[N];
int n,s=0,ans=inf;
int x[N],y[N];
int l[N][N]={0};
void init(int pt,int num){
    if (num>=ans)return ;
    if (pt==n+1){
        ans=min(ans,num);
        return ;
    }
    init(pt+1,num+2*l[0][pt]);
    for (int i=1;i<pt;i++){
        if (ok[i]==0&&l[0][i]>l[i][pt]-l[0][pt]){
            ok[i]=ok[pt]=1;
            init(pt+1,num-l[0][i]+l[i][pt]+l[0][pt]);
            ok[i]=ok[pt]=0;
        }
    }
    return ;
}
int main(){
    freopen ("lenepack.in","r",stdin);
    freopen ("lenepack.out","w",stdout);
    scanf("%d%d",&x[0],&y[0]);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
    for (int i=0;i<=n;i++){
        for (int j=0;j<=n;j++){
            if (i==j)continue;
            l[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
        }
    }
    init(1,0);
    printf("%d\n",ans);
    return 0;
}