次短路算法模板

次短路算法模板。
链接的算法是算严格比最短路大的次短路，且可以重复经过点。
用两边djikstra的方法算出可以经过重复点的最短路
集合位置
这题是不可以经过重复点的可以和最短路一样长的次短路。用删边求最短路可以ac。
但是用第一个链接中的算法加上重复点判重可以过80分。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;
const int M=200010;
int head[M],cnt;
int path1[M], path2[M];
int tag[M];
struct node
{
    double v,w,nxt;
}edge[M];
double dis1[5050];
double disn[5050];
int vis[5050];
bool st[M];
    int n,r;
void add(int x,int y,double w)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    edge[cnt].w=w;
    head[x]=cnt;
}
struct pt{
    double x, y;
}p[M];
double s(pt a, pt b)
{
    return sqrt((a.x - b. x) * (a.x - b. x) + (a.y - b.y) * (a.y - b.y));
}
void Dijkstra(int x,double dis[ ], int path[])
{
    memset(vis,0,sizeof(vis));
    priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >qu;
    dis[x]=0;
    qu.push(make_pair(0,x));
    while(!qu.empty( ))
    {
        int u=qu.top( ).second;
        qu.pop( );
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u];i!=-1;i=edge[i].nxt)
            {
                int v=edge[i].v;
                if(dis[v]>dis[u]+edge[i].w)
                {
                    dis[v]=dis[u]+edge[i].w;
                    path[v] = u;
                    qu.push(make_pair(dis[v],v));
                }
            }
        }
    }
}
bool check(int x, int y)
{
    memset(st, 0 ,sizeof st);
    st[x] = true;
    while(x != 1)
    {
        x = path1[x];
        if(!st[x])st[x] = true;
        else return 0;

    }
    st[y] = true;
    while(y != n)
    {
        y = path2[y];
        if(!st[y])st[y] = true;
        else return 0;
    }
    return 1;
}
void sht()
{
    int x = n;
    tag[n] = true;
    while(x != 1)
    {
        x = path1[x];
        tag[x] = true;
    }
    tag[1] = true;
}
bool check2(int x, int y)
{
    if(tag[x])return 0;
    while(x != 1)
    {
        x = path1[x];
        if(tag[x])return 0;
    }
    if(tag[y])return 0;
    while(y != n)
    {
        y = path2[y];
        if(tag[y])return 0;
    }
    return 1;
}
int main( )
{

    scanf("%d%d",&n,&r);
    memset(head,-1,sizeof(head));
    cnt=0;
    int x,y,w;
    for(int i = 1; i <= n; i++)
    {
        double a, b;
        cin >> a>> b;
        p[i] = {a, b};
    }
    for(int i = 0; i < r; i++)
    {
        int a, b;
        cin >> a>> b;
        double t = s(p[a], p[b]);
        add(a, b, t);
        add(b, a, t);
    }
   for(int i = 1; i <= n; i++)
    {
       dis1[i] = disn[i] = INF;
    }
    Dijkstra(1,dis1, path1);
    Dijkstra(n,disn, path2);
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dis1[i]<<" ";
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<disn[i]<<" ";
    // }
    // cout<<endl;
    double ans=dis1[n];
    double temp=INF;
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j!=-1;j=edge[j].nxt)
        {
            int v=edge[j].v;
            double w=dis1[i]+edge[j].w+disn[v];
            if(w == ans)
            {
                if(!check(i, v)){
                        temp = w;
                        break;
                }
            }
            else
            {
                if(temp > w && check(i, v))
                    temp = w;
            }

        }
        if(temp == ans)break;
    }
    printf("%.2lf", temp);
    return 0;
}