记录编号	516833	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Oct08] 被破坏的电力系统	最终得分	100
用户昵称	Chtholly	是否通过	通过
代码语言	C++	运行时间	0.208 s
提交时间	2018-10-26 15:06:34	内存使用	85.76 MiB

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct con{
	double x,y;
} edge[100005];
struct Node{
	int nex,to;
	double num;
} a[5000005];
int total,f[maxn],vis[maxn],n,w;
double dis[maxn],m;
priority_queue<pair< int , int > > q;
void dijkstra(int s){
	memset(dis,9999999,sizeof(dis));
	dis[s]=0;
	q.push(make_pair(-dis[s],s));
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=f[x];i;i=a[i].nex){
			int j=a[i].to;
			if(!vis[j]&&dis[j]>dis[x]+a[i].num) 
				dis[j]=dis[x]+a[i].num,q.push(make_pair(-dis[j],j));
		}
	}
}
void Add_edge(int u,int v,double dist){
	a[++total].nex=f[u],a[total].to=v,a[total].num=dist,f[u]=total;
}
double DIS(int i,int j){
	 double x1,x2,y1,y2;
	 x1=edge[i].x;y1=edge[i].y;
	 x2=edge[j].x;y2=edge[j].y;
	 double ans=hypot(x1-x2,y1-y2);
	 return ans;
}
int main()
{
	freopen("pwrfail.in","r",stdin);
	freopen("pwrfail.out","w",stdout);
	cin>>n>>w>>m;
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&edge[i].x,&edge[i].y);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)
			if(DIS(i,j)<=m) Add_edge(i,j,DIS(i,j)),Add_edge(j,i,DIS(i,j));
	}
	int x,y;
	for(int i=1;i<=w;i++){
		scanf("%d%d",&x,&y);Add_edge(x,y,0),Add_edge(y,x,0);
	}
	dijkstra(1);
	if(dis[n]>9999990) cout<<"-1";
	else cout<<int(dis[n]*1000);
}