2942139_ac_124ms_236k.cpp

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

#include "stdio.h"
#include "math.h"
#include "string.h"
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
	double x, y;
}pos[1010];
int no;

int visited[1010];
vector <int> map[1010];
queue <int> que;

double dis(int i,int j)
{
	return sqrt((pos[i].x-pos[j].x)*(pos[i].x-pos[j].x)+(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y));
}

void bfs()
{
	int t, i;

	memset(visited,-1,sizeof(visited));
	que.push(0);
	visited[0] = 0;
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		for(i = 0; i < map[t].size(); i++)
		{
			if(visited[map[t][i]]==-1)
			{
				visited[map[t][i]] = visited[t]+1;
				que.push(map[t][i]);
			}
		}
	}
	if(visited[no-1]==-1)
		puts("No.");
	else
	{
		printf("Yes, visiting %d other holes.\n",visited[no-1]-1);
	}
}

int main()
{
	double v, m;
	double x, y, d;
	int i, j;

	scanf("%lf%lf",&v,&m);
	m *= 60;
	scanf("%lf%lf",&pos[0].x,&pos[0].y);
	scanf("%lf%lf",&x,&y);
	no = 1;
	while(scanf("%lf%lf",&pos[no].x,&pos[no].y)==2)
	{
		no++;
	}
	pos[no].x = x;pos[no].y = y;
	no++;
	for(i = 0; i < no; i++)
	{
		for(j = i+1; j < no; j++)
		{
			d = dis(i,j);
			d /= v;
			if(d <= m)
			{
				map[i].push_back(j);
				map[j].push_back(i);
			}
		}
	}
	bfs();
	return 0;
}