记录编号	512637	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Oct08] 被破坏的电力系统	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2018-10-05 20:05:32	内存使用	4.24 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
priority_queue<pair<double,int> >q;
vector<int>b[1010];
vector<double>c[1010];
int n,m,a1,a2,x[1010],y[1010],mp[1010][1010],ju=1;
double s,dis[1010],a3;
bool bk[1010];
int main(){
	freopen("pwrfail.in","r",stdin);
	freopen("pwrfail.out","w",stdout);
	scanf("%d%d%lf",&n,&m,&s);
	for(int i=2;i<=n;i++)dis[i]=999999.0;
	for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=m;i++){
	    scanf("%d%d",&a1,&a2);
		b[a1].push_back(a2);
		b[a2].push_back(a1);
		c[a1].push_back(0.0);
		c[a2].push_back(0.0);
		mp[a1][a2]=mp[a2][a1]=1;
	}
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
		    if(i!=j&&!mp[i][j]){
			    double g=(double)sqrt((x[i]-x[j])*1.0*(x[i]-x[j])+(y[i]-y[j])*1.0*(y[i]-y[j]));
				if(g*1000000<=s*1000000){
			        b[i].push_back(j);
		            c[i].push_back(g);			    
				}
			}
		}
	}
	q.push(make_pair(0,1));
	while(q.size()){
	    a1=q.top().second;q.pop();
		if(a1==n){ju=0;continue;}
		if(bk[a1])continue;
		bk[a1]=1;
		for(int i=0;i<b[a1].size();i++){
		    a2=b[a1][i];a3=c[a1][i];
			if(!bk[a2]&&dis[a1]+a3<dis[a2]){
			    dis[a2]=dis[a1]+a3;
				q.push(make_pair(-dis[a2],a2));
			}
		}
	}
	if(ju){printf("-1");return 0;}
	else printf("%d",(int)(1000*dis[n]));
	return 0;
}