2092011_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <math.h>
# include <string.h>

struct node
{
	int x;
	int y;
}beeper[11];

void input()
{
	int i, j, min;
	int n, no;
	int x, y;
	int r, l;
	int mark[11], m, ans, t;

	scanf("%d",&n);
	while(n--)
	{
		min = 30000;ans = 0;
		memset(mark,0,sizeof(mark));
		scanf("%d%d%d%d",&r,&l,&x,&y);
		scanf("%d",&no);
		for(i = 0; i < no; i++)
		{
			scanf("%d%d",&beeper[i].x,&beeper[i].y);
			if(abs(beeper[i].x-x)+abs(beeper[i].y-y)<min)
			{
				min = abs(beeper[i].x-x)+abs(beeper[i].y-y);
				m = i;
			}
		}
		mark[m] = 1;
		ans += min;
		for(j = 1; j < no; j++)
		{
			min = 30000;
    		for(i = 0; i < no; i++)
			{
				if(mark[i]==0&&abs(beeper[i].x-beeper[m].x)+abs(beeper[i].y-beeper[m].y)<min)
				{
			    	min = abs(beeper[i].x-beeper[m].x)+abs(beeper[i].y-beeper[m].y);
			    	t = i;
				}
			}
			mark[t] = 1;
			ans += min;
			m = t;
		}
		ans += abs(beeper[m].x-x)+abs(beeper[m].y-y);
		printf("The shortest path has length %d\n",ans);
	}
}

int main()
{
	input();
	return 1;
}