比赛 |
SYOI2022 Round2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Looking for Order |
最终得分 |
100 |
用户昵称 |
锝镆氪锂铽 |
运行时间 |
1.166 s |
代码语言 |
C++ |
内存使用 |
133.74 MiB |
提交时间 |
2022-06-17 10:17:52 |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define tim2(x) (x * x)
using namespace std;
const int INF = 0x3f3f3f3f, maxN = 1 << 24;
void DP();
int cnt, n;
int dp[maxN], dis[25][25], pres[maxN];
pair <int, int> a[25];
int main(void){
freopen("lenepack.in", "r", stdin);
freopen("lenepack.out", "w", stdout);
int x, y;
scanf("%d%d", &x, &y);
scanf("%d", &n);
a[n] = make_pair(x, y);
for (int i = 1; i <= n; i ++){
scanf("%d%d", &x, &y);
a[i - 1] = make_pair(x, y);
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j ++)
dis[i][j] = tim2((a[i].first - a[j].first)) + tim2((a[i].second - a[j].second));
DP();
printf("%d\n", dp[(1 << n) - 1]);
//system("pause");
return 0;
}
void DP(){
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < (1 << n); i ++){
if (dp[i] == INF)
continue;
for (int j = 0; j < n; j ++){
if (((1 << j) & i) == 0){
for (int k = j; k < n; k ++){
if (((1 << k) & i) == 0){
int tmp = i | (1 << j) | (1 << k);
int d = dis[j][k] + dis[n][j] + dis[n][k];
if (dp[tmp] > dp[i] + d){
dp[tmp] = dp[i] + d;
pres[tmp] = i;
}
}
}
break;
}
}
}
}