请在 spfa 或 dijkstra 取出新点并弹出,且修改了 vis 数组的值(仅 spfa)后,判断一下这个点是不是 n ,如果是,请 continue 。
另外,为什么#6老是 WA 啊,有人帮我调一调吗,我感觉各种特判都写了啊,我的输出是 0 ,不知道为什么,这题也没公开数据。
给出一组 Hack 也行啊啊啊啊
附上我的代码:
#include<bits/stdc++.h>
using namespace std;
const int size=50100;
int n,m,s,t,tot=0;
int ver[size],head[size],nxt[size];
double d1[size],d2[size],edge[size],d[size];
int pre1[size],pre2[size];
int v[size];
struct point{
double x,y;
inline void input(){cin>>x>>y;}
}p[size];
inline double dis(point x,point y){
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
inline void add(int x,int y,double z){
ver[++tot]=y;
edge[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
inline void spfa(){
queue<int> q;
for(int i=0;i<=n+1;++i) d1[i]=d2[i]=1e9;
memset(v,0,sizeof(v));
q.push(1);
d1[1]=0;v[1]=1;
while(!q.empty()){
int x=q.front();q.pop();
v[x]=0;
if(x==n) continue;
if(d1[x]>=1e9-1e6) continue;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
double z=edge[i];
if(d1[y]>d1[x]+z){
d2[y]=d1[y];
d1[y]=d1[x]+z;
if(!v[y]) v[y]=1,q.push(y);
}
if(d2[y]>d2[x]+z){
d2[y]=d2[x]+z;
if(!v[y]) v[y]=1,q.push(y);
}
if(d2[y]>d1[x]+z&&d1[y]<d1[x]+z){
d2[y]=d1[x]+z;
if(!v[y]) v[y]=1,q.push(y);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i) p[i].input();
for(int i=1;i<=m;++i){
int u,v;
cin>>u>>v;
if(u==v) continue;
double w=dis(p[u],p[v]);
add(u,v,w);
add(v,u,w);
}
spfa();
if(d2[n]>=1e9-1e-6) cout<<-1;
else printf("%.2lf\n",d2[n]);
return 0;
}