2861389_wa.c

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

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

int map[1001][1001];
struct node
{
	int x, y;
}out[1001];

int que[1001];
int step[1001];
int f, r, n;
int visited[1001];

void bfs(int st,int ed)
{
	int i, t, w;

	f = r = -1;
	memset(visited,0,sizeof(visited));
	visited[st] = 1;
	que[++r] = st;
	step[r] = 0;
	while(f!=r)
	{
		++f;
		t = que[f];
		w = step[f];
		for(i = 1; i <= map[t][0]; i++)
		{
			if(!visited[map[t][i]])
			{
				visited[map[t][i]] = 1;
				que[++r] = map[t][i];
				step[r] = w+1;
				if(map[t][i]==ed)
				{
					printf("%d\n",w+1);
					return ;
				}
			}
		}
	}
	puts("Impossible");
}

int main()
{
	int cas;
	int st, ed;
	int i, j, l;
	double len1, len2;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d%d%lf%lf",&n,&st,&ed,&len1,&len2);
		len1 += len2;
		len1 *= len1;
		l = (int)ceil(len1);
		for(i = 1; i <= n; i++)
			scanf("%d%d",&out[i].x,&out[i].y);
		memset(map,0,sizeof(map));
		for(i = 1; i <= n; i++)
		{
			for(j = i+1; j <= n; j++)
			{
				if((out[i].x-out[j].x)*(out[i].x-out[j].x)+(out[i].y-out[j].y)*(out[i].y-out[j].y)<=l)
				{
					map[i][0]++;
					map[i][map[i][0]] = j;
					map[j][0]++;
					map[j][map[j][0]] = i;
				}	
			}
		}
		bfs(st,ed);
	}
	return 0;
}