题目描述

每次有大的活动，大家都要在一起“聚一聚”，不管是去好乐迪，还是避风塘，或者汤姆熊，大家都要玩的痛快。

还记得心语和花儿在跳舞机上的激情与释放，还记得草草的投篮技艺是如此的高超，还记得狗狗的枪法永远是'S'……还有不能忘了，胖子的歌声永远是让我们惊叫的！！

今天是野猫的生日，所以想到这些也正常，只是因为是上学日，没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。

但是每次集合的时候都会出现问题！野猫是公认的“路盲”，野猫自己心里也很清楚，每次都提前出门，但还是经常迟到，这点让大家很是无奈。后来，野猫在每次出门前，都会向花儿咨询一下路径，根据已知的路径中，总算能按时到了。

现在提出这样的一个问题：给出n个点的坐标，其中第一个为野猫的出发位置，最后一个为大家的集合位置，并给出哪些位置点是相连的。野猫从出发点到达集合点，总会挑一条最近的路走，如果野猫没找到最近的路，他就会走第二近的路。请帮野猫求一下这条第二最短路径长度。

原题链接

Solve

1.次短路+SPFA。

2.SPFA找最短路，并记录路径。

3.删去最短路径中的一条边，并用SPFA寻找最短路。

4.重复3的步骤，其中最小值即为答案。

Tip

1.此题并不是严格次短路，即答案可能与最短路的值相同。

2.步骤3中SPFA完成之后别忘了还原回去。

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 336860180  //定义一个最大范围
#define N 100000 
using namespace std;  //标准开头
int n,m,len;  //n,m-同题，len-邻接表边数
double x[N],y[N],dis[N],ans1,ans2=maxn;  //x,y-点的坐标，dis-最短路，ans1-最短路，ans2-步骤3中的最小值
int e,r;  //边的两点
int first[N],next[N],f[N][3];  //first,next-邻接表，f[i][1]-节点i的前驱边，f[i][2]-节点i的前驱点
bool vis[N];  //SPFA中的bool数组
struct note{  //邻接表
   int v;
   double w;
   bool fb;  //若fb为true,则此边已删
}d[N];
double dist(double x1,double y1,double x2,double y2){  //两点求距离
   return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void add(int e,int r,double distt){  //建立邻接表
   d[++len].v=r;
   d[len].w=distt;
   next[len]=first[e];
   first[e]=len;
}
void spfa()  //步骤2的SPFA
{
   for(int i=1;i<=n;i++) dis[i]=maxn;
   memset(vis,false,sizeof(vis));
   dis[1]=0;
   queue<int> q;
   q.push(1);
   while(!q.empty()){
   	int e=q.front();
   	q.pop();
   	vis[e]=false;
   	for(int i=first[e];i!=-1;i=next[i]){
   		if(dis[d[i].v]>dis[e]+d[i].w){
   			f[d[i].v][1]=e;
   			f[d[i].v][2]=i;
   			dis[d[i].v]=dis[e]+d[i].w;
   			if(!vis[d[i].v]){
   				vis[d[i].v]=true;
   				q.push(d[i].v);
   			}
   		}
   	}
   }
}
void spfaa()  //步骤3中的SFPA
{
   for(int i=1;i<=n;i++) dis[i]=maxn;
   memset(vis,false,sizeof(vis));
   dis[1] = 0;
   queue<int> q;
   q.push(1);
   while(!q.empty()){
   	int e=q.front();
   	q.pop();
   	vis[e]=false;
   	for(int i=first[e];i!=-1;i=next[i]){
   		if(dis[d[i].v]>dis[e]+d[i].w&&!d[i].fb){
   			dis[d[i].v]=dis[e]+d[i].w;
   			if(!vis[d[i].v]){
   				vis[d[i].v]=true;
   				q.push(d[i].v);
   			}
   		}
   	}
   }
}
int main()
{
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++) cin>>x[i]>>y[i],first[i]=-1;
   for(int i=1;i<=m;i++){
   	scanf("%d%d",&e,&r);
   	add(e,r,dist(x[e],y[e],x[r],y[r]));
   	add(r,e,dist(x[e],y[e],x[r],y[r]));
   }
   spfa();
   int s=n;
   ans1=dis[n];
   if(ans1==maxn){
   	cout<<"-1";
   	return 0;
   }
   while(s!=1){
   	d[f[s][2]].fb=true;
   	spfaa();
   	if(ans1==dis[n]){
   		printf("%.2lf",ans1);
   		return 0;
   	}
   	d[f[s][2]].fb=false;  //还原
   	s=f[s][1];
   	ans2=min(ans2,dis[n]);
   }
   if(ans2==maxn) cout<<"-1";
   else printf("%.2lf",ans2);
   return 0;
}