记录编号	298100	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Oct08] 被破坏的电力系统	最终得分	100
用户昵称	open the window	是否通过	通过
代码语言	C++	运行时间	0.230 s
提交时间	2016-08-20 10:05:01	内存使用	9.87 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const double INF=999999999.0;
int p,q,e,n,o,t=0,w=1;
long long ans;
int h[200006];
double x[1011],y[1011],m;
bool v[1011],b[1011][1011];
double f[1011][1011],dis[1011];
int main()
{
	freopen("pwrfail.in","r",stdin);
	freopen("pwrfail.out","w",stdout);
	for (int i=0; i<1001; ++i) dis[i]=9999999999.000;
	scanf("%d%d%lf",&n,&o,&m); 
	for (int i=1; i<=n; ++i) scanf("%lf%lf",&x[i],&y[i]);
	for (int i=1; i<=o; ++i) 
	{
	   scanf("%d%d",&p,&q);
	   b[p][q]=b[q][p]=true;
    }
	for (int i=1; i<=n; ++i)
	 for (int j=i; j<=n; ++j)
	  if (b[i][j]) f[i][j]=f[j][i]=0;
	   else 
	   {
	   	  f[i][j]=f[j][i]=sqrt((long double)(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		  if (f[i][j]>m) f[i][j]=f[j][i]=9999999999.000;
	   }
	h[1]=1; dis[1]=0.000; v[1]=true;
	while (t<w)
	{
		t++;
		e=h[t];
		for (int i=1; i<=n; ++i)
		 if (dis[i]>dis[e]+f[e][i])
		  {
			 dis[i]=dis[e]+f[e][i];
			 if (!v[i])
			 {
			 	v[i]=true;
			 	w++;
			 	h[w]=i;
			 }
		  }
		v[e]=false;
	}
	if (dis[n]==9999999999.000) cout<<"-1"<<endl;
	 else cout<<(long long)(dis[n]*1000.000)<<endl;
}