Miscellany

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX 15
const int inf = 2000000000;
int TC;
int x[MAX],y[MAX];
int W,H;
int xs,ys;
int  n;
int dp[ (1<<10) ][MAX];

int dist(int i1, int i2){
	return abs(x[i1]-x[i2]) + abs(y[i1]-y[i2]);
}

int rec(int mask,int cur){
	if (dp[mask][cur] != -1) return dp[mask][cur];
	int &res = dp[mask][cur];
	res = inf;
	if (mask == (1<<n)-1){
		res = dist(cur,0);
	}else{
		for (int i = 1; i <= n; i++)
			if (!((mask>>(i-1))&1)){
				res = min(res,dist(cur,i) + rec(mask|(1<<(i-1)),i));
			}
	}
	return res;
};

int main(){
	scanf("%d",&TC);
	while (TC--){
		scanf("%d%d",&W,&H);
		scanf("%d%d",&x[0],&y[0]);
		scanf("%d",&n);
		for (int i = 1; i <= n; i++) scanf("%d%d",&x[i],&y[i]);
		memset(dp, -1, sizeof dp);
		printf("The shortest path has length %d\n",rec(0,0));
	}
}