今天在PKU上做了我第一題廣度優(yōu)先搜索題：
Problem Id:2627??User Id:beyonlin_SCUT
Memory:64K??Time:575MS
Language:C++??Result:Accepted
個(gè)人認(rèn)為算法復(fù)雜度應(yīng)該為O(n^2)或更小。不知是不是這樣。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2627

Gopher and hawks
Time Limit:1000MS? Memory Limit:65536K
Total Submit:900 Accepted:328

Description
A gopher sits in a hole located at (xs, ys) and wants to get to a hole located at (xt, yt). The gopher can run at a constant speed of v m/sec. However, if the gopher is outside of a hole for more than a m minutes he will become a supper to hawks flying over the holes. Can the gopher make it?

Input
The first line of input contains two positive integer numbers: v -- gopher's speed in meters per second and m -- the time after which the gopher becomes prey to hawks if he stays outside a hole. The second line of input contains two floating point numbers: the (xs,ys) coordinates of the gopher starting hole. The third line contains the (xt, yt) coordinates of the target hole. Each Subsequent line of input contains two floating point numbers: the (x,y) coordinates of a gopher hole. All distances are in metres, to the nearest mm.

Output
If the gopher can make it to the target hole, the output line should read "Yes, visiting n other holes.", where n is the minimal number of intermediate holes the gopher has to visit. If the gopher cannot make it the output line should read "No." There are not more than 1000 gopher holes and all coordinates are between -10000 and +10000.

Sample Input

3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000

Sample Output

Yes, visiting 2 other holes.

Hint
Sample input 2
5 1
0.000 0.000
0.000 550.000
179.000 0.000
0.000 301.000

Output for sample input 2
No.

我的程序：
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
struct node
{
	int point;
	int step;
};
double x[1100],y[1100];
bool flag[1100]={false};
int main()
{
	int i,v,t;
	scanf("%d%d",&v,&t);
	t*=60;
	double beginX,beginY,endX,endY;
	scanf("%lf%lf%lf%lf",&beginX,&beginY,&endX,&endY);
	int n=1;
	while(scanf("%lf%lf",x+n,y+n)!=EOF)
		n++;
	x[0]=beginX;
	y[0]=beginY;
	x[n]=endX;
	y[n]=endY;

	node n1;//隊(duì)列初始化
	n1.point=0;
	n1.step=0;
	queue<node> que;
	que.push(n1);

	int steps=0;
	while(true)
	{
		if(que.empty())
			break;
		node tmp=que.front();
		que.pop();//出隊(duì)列
		for(i=1;i<=n;i++)
		{
			if(!flag[i])//標(biāo)志是否進(jìn)過隊(duì)列
			{				
				double time=sqrt(pow(x[i]-x[tmp.point],2.0)+pow(y[i]-y[tmp.point],2.0))/v;
				if(time<t)
				{
					if(i==n)
					{
						steps=tmp.step;
						goto next;
					}
					else
					{
						node in;
						in.point=i;
						in.step=tmp.step+1;
						que.push(in);//進(jìn)隊(duì)列
						flag[i]=true;
					}
				}
			}
		}
	}
	next:
	if(steps!=0)
		printf("Yes, visiting %d other holes.\n",steps);
	else
		printf("No.\n");
	return 0;
}