pku2907.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 66 行

#include <stdio.h>
#include <string.h>
#define INF 100000000

typedef struct Point
{
	int x, y;
}Point;

Point p[10];
int N, X, Y;
int d[10][10];
int v[10];
int min;

int abs(int x) {return x > 0 ? x : -x;}
int dis(const Point &a, const Point &b){return abs(a.x - b.x) + abs(a.y - b.y);}

void DFS(int p, int sum, int k)
{
	int i;
	if (sum >= min || (p == 0 && k != N))
		return;
	if (k == N && p == 0)
	{
		if (sum < min)
			min = sum;
		return;
	}
	v[p] = 1;
	for (i = 0; i <= N; i++)
	{
		if (!v[i])
			DFS(i, sum + d[i][p], k + 1);
	}
	v[p] = 0;
}

void Solve()
{
	int i, j;
	scanf("%d %d", &X, &Y);
	scanf("%d %d", &p[0].x, &p[0].y);
	scanf("%d", &N);
	for (i = 1; i <= N; i++)
		scanf("%d %d", &p[i].x, &p[i].y);
	for (i = 0; i <= N; i++)
		for (j = 0; j <= N; j++)
			d[i][j] = dis(p[i], p[j]);
	memset(v, 0, sizeof(v));
	min = INF;
	for (i = 1; i <= N; i++)
		DFS(i, d[i][0], 0);
	printf("The shortest path has length %d\n", min);
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
		Solve();
	return 0;
}