【题解】洛谷P2914[USACO08OCT]断电Power Failure

洛谷P2914：https://www.luogu.org/problemnew/show/P2914

哇

这题目在暑假培训的时候考到

当时用Floyed会T掉

看楼下都是用Dijkstra

难道没有人用优雅的SPFA吗？

思路

用前向星构建整个图

注意每一条边都不能超过len（也就是题目中的m）

所以存图的时候注意一下这一点就行了

其他就跟SPFA一样套板子

代码中还有详细注解

注意坑点：数组开大一点 没开大的我RE了2次

代码

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n,m,cnt;

double len;

int exist[500005];//判断是否在队中

int team[2000020];//队列

int head[500005];

double dis[500005];//从1到n的距离

int t=0,w=1;

struct ele

{

	double x;

	double y;

}ele[100005];//电线杆的坐标

struct edge

{

	int next;

	int to;

	double w;

}e[5000005];

void add(int u,int v,double w)

{

	e[++cnt].w=w;

	e[cnt].to=v;

	e[cnt].next=head[u];

	head[u]=cnt;

}//前向星图

double dist(int i,int j)

{

    double x1=ele[i].x;

    double y1=ele[i].y;

    double x2=ele[j].x;

    double y2=ele[j].y;

    double d=hypot(x1-x2,y1-y2);//判断电线杆之间的距离

	                            //据楼下的dalao说用sqrt会爆就没用

								//用了求直角三角形斜边长的函数<cmath>

    return d;

}

int main()

{

	cin>>n>>m>>len;

	for(int i=1;i<=n;i++)

	cin>>ele[i].x>>ele[i].y;

	for(int i=1;i<=n;i++)

	dis[i]=99999999;//初始化

	for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	{

		if(dist(i,j)<=len)//如果没有超过len就可以加入边

        {

			add(i,j,dist(i,j));

		    add(j,i,dist(i,j));

		}

	}

	for(int i=1;i<=m;i++)

    {

        int x,y;

        cin>>x>>y;

        add(x,y,0);

		add(y,x,0);//如果已经有电线就不用再花费距离

    }

    dis[1]=0;//常规SPFA开始

    team[1]=1;

    while(t<w)

    {

		t++;

		int u=team[t];

		exist[u]=0;

		for(int i=head[u];i;i=e[i].next)

		{

			int v=e[i].to;

			if(dis[v]>dis[u]+e[i].w)

			{

				dis[v]=dis[u]+e[i].w;

				if(!exist[v])

				{

					w++;

					exist[v]=1;

					team[w]=v;

				}

			}

		}

	}

	if(dis[n]==99999999)//如果到不了

	cout<<"-1";

	else

	cout<<int(dis[n]*1000);//强制转换int类型

}