这道题数据怎么会这么坑……
从20，到50，到80，再到AC，经历了三天时间……
这道题不用判断是否没有路……（数据没有，净想着坑人了）
看到洛谷上很多人都抱怨数据太强，自己的算法就是过不了，在这里我就分享一下自己的算法（你可能之前没看过，原创）：
首先，对于Dijkstra的记录，我们会需要一个新数组来记录次短路，并且两个点的最短路，次短路在一定情况下要互相更新。
如果只用最短路分别更新的话，有的点是没有次短路的（自己想个图）。
其次，如果你不开vis，你会开开心心地T八个点~~~
别问我是怎么知道的。
然后，就是一开始考虑最短路更新最短路，如果可以次短路继承原来的最短路，再考虑次短路更新次短路；
最后还有一个巨大的坑……
到终点后，你还要用这个值去更新别人嘛……
注意以上n点，你就过了这道题……
#include<cstdio> #include<queue> #include<cmath> #include<algorithm> #include <iostream> using namespace std; #define maxn 50005 #define INF 99999999 priority_queue < pair<double,int> > q; int n,m,cnt,head[maxn]; double dis[maxn],sec[maxn]; bool vis[maxn]; struct node { int to,nxt; double w; } c[maxn]; struct point { int x,y; } num[maxn]; void add(int a,int b) { c[++cnt].to=b; c[cnt].nxt=head[a]; head[a]=cnt; c[cnt].w=sqrt((double)pow(num[a].x-num[b].x,2) +pow(num[a].y-num[b].y,2)); } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) dis[i]=INF,sec[i]=INF; for(int i=1; i<=n; i++) scanf("%d%d",&num[i].x,&num[i].y); for(int i=1; i<=m; i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dis[1]=0; //sec[1]=0; q.push(make_pair(0,1)); while(!q.empty()) { int p=q.top().second; q.pop(); if(vis[p]) continue; vis[p]=1; if(p==n) continue; if(dis[p]==INF) continue; for(int i=head[p]; i; i=c[i].nxt) { int v=c[i].to; if(dis[p]+c[i].w<dis[v]) { sec[v]=dis[v]; dis[v]=dis[p]+c[i].w; q.push(make_pair(-dis[v],v)); if(sec[p]+c[i].w<sec[v]) sec[v]=sec[p]+c[i].w; } else if(dis[p]+c[i].w<sec[v]) sec[v]=dis[p]+c[i].w; } } if(sec[n]==INF) { printf("-1"); return 0; } else printf("%.2lf",sec[n]); return 0; }