集合位置（次短路模板题）

​​传送门​​

这道题就是次短路的模板题，思路很简单，先求最短路，然后枚举最短路的每一条边，每次删去一条，然后再求最短路，对于这几次结果取最小值即可。
本质的理论就是最短路和次短路（如果存在的话）是不可能重合的，也许长度相等。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=205,maxm=20005;
struct Edge{
  int u,v;
  double w;
  Edge(int u,int v,double w):u(u),v(v),w(w){}
};
double d[maxn],ans=2000000000.0,shortest=2000000000.0;
int n,m;
int xx[maxn],yy[maxn],inq[maxn],p[maxn];
vector<int> G[maxn];
vector<Edge> edge;
queue<int> Q;
stack<int> S;
int d1,d2;
void bfs(){
  d[1]=0;
  memset(inq,0,sizeof(inq));
  memset(p,-1,sizeof(p));
  Q.push(1);
  inq[1]=1;
  while(!Q.empty()){
    int cur=Q.front();
    Q.pop();
    inq[cur]=0;
    for(int i=0;i<G[cur].size();i++){
      Edge& e=edge[G[cur][i]];
      if(e.v==n){
        if(d[e.v]>d[cur]+e.w){
          d[e.v]=d[cur]+e.w;
          p[n]=cur;
        }
      }else if(d[e.v]>d[cur]+e.w){
        d[e.v]=d[cur]+e.w;
        p[e.v]=cur;
        if(!inq[e.v]){
          Q.push(e.v);
          inq[e.v]=1;
        }
      }
    }
  }

} 
void sec_shortest(){
  for(int i=1;i<=n;i++){
    d[i]=2000000000.0;
  }
  d[1]=0;
  memset(inq,0,sizeof(inq));
  Q.push(1);
  inq[1]=1;
  while(!Q.empty()){
    int cur=Q.front();
    Q.pop();
    inq[cur]=0;
    for(int i=0;i<G[cur].size();i++){
      Edge& e=edge[G[cur][i]];
      if(cur==d1&&e.v==d2){
        continue;
      }
      if(e.v==n){
        if(d[e.v]>d[cur]+e.w){
          d[e.v]=d[cur]+e.w;
        }
      }else if(d[e.v]>d[cur]+e.w){
        d[e.v]=d[cur]+e.w;
        if(!inq[e.v]){
          Q.push(e.v);
          inq[e.v]=1;
        }
      }
    }
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    scanf("%d%d",&xx[i],&yy[i]);
    d[i]=2000000000.0;
  }
  for(int i=0;i<m;i++){
    int u,v;
    scanf("%d%d",&u,&v);
    edge.push_back(Edge(u,v,sqrt(pow(xx[v]-xx[u],2)+pow(yy[v]-yy[u],2))));
    G[u].push_back(2*i);
    edge.push_back(Edge(v,u,sqrt(pow(xx[v]-xx[u],2)+pow(yy[v]-yy[u],2))));
    G[v].push_back(2*i+1);
  }
  bfs();
  shortest=d[n];
  int cur=n;
  S.push(cur);
  while(p[cur]!=-1){
    S.push(p[cur]);
    cur=p[cur];
  }
  d1=S.top();
  S.pop();
  d2=S.top();
  S.pop();
  sec_shortest();
  if(d[n]<ans){
    ans=d[n];
  }
  while(!S.empty()){
    d1=d2;
    d2=S.top();
    S.pop();
    sec_shortest();
    if(d[n]<ans){
      ans=d[n];
    }
  }
  if(ans>1999999999.0){
    printf("-1");
  }else{
    printf("%.2lf",ans);
  }

  return 0;
}