记录编号	571736	评测结果	AAAAAAAAAA
题目名称	[CF8C]Looking for Order	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.792 s
提交时间	2022-06-17 10:18:59	内存使用	133.74 MiB

#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;
			}
		}
	}
}