记录编号	106703	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Oct08] 被破坏的电力系统	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.241 s
提交时间	2014-06-18 14:18:23	内存使用	8.93 MiB

#include<fstream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
ifstream fin("pwrfail.in");
ofstream fout("pwrfail.out");
const double INF=999999999.0;
queue<int> q;
class woca
{
public:
	long long x;
	long long y;
}M[1001];
double map[1001][1001];
bool flag[1001][1001];
int n,m;
double X;
////////开始
double dist[1001];
bool BO[1001];//是否在队中
void SPFA(int a)
{
	int temp,i;
	q.push(a);
	dist[a]=0;
	BO[a]=1;
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		for(i=1;i<=n;i++)
		{
			if(dist[i]>dist[temp]+map[temp][i])
			{
				dist[i]=dist[temp]+map[temp][i];
				if(BO[i]==0)
				{
					q.push(i);
					BO[i]=1;
				}
			}
		}
		BO[temp]=0;
	}
}
int main()
{
	fin>>n>>m>>X;
	int i,j;
	memset(flag,0,sizeof(flag));
	int A,B,C,D,E,F;//最后的AB为终点坐标,CD为起点坐标
	for(i=1;i<=n;i++)
	{
		fin>>A>>B;
		if(i==1)
		{C=A;D=B;}
		M[i].x=A;M[i].y=B;
		dist[i]=INF;
	}
	for(i=1;i<=m;i++)
	{
		fin>>E>>F;
		flag[E][F]=1;
		flag[F][E]=1;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			map[i][j]=INF;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(flag[i][j]==1)
				map[i][j]=0;
			else
				{
					map[i][j]=sqrt(double((M[i].x-M[j].x)*(M[i].x-M[j].x)+(M[i].y-M[j].y)*(M[i].y-M[j].y)));
					if(map[i][j]>X)
						map[i][j]=INF;
			    }
		}
	SPFA(1);
	if(dist[n]==INF)
	{
		fout<<-1<<endl;
		return 0;
	}
	fout<<int(dist[n]*1000)<<endl;
	return 0;
}