洛谷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类型
}
转载于:https://www.cnblogs.com/BrokenString/p/9296720.html
