Topic link: https://cn.vjudge.net/contest/314508#problem/A
Translator: ____________. The countryside is composed of R (1 < R < 100000) two-way roads. Each road connects two of N (1 < N < 5000) intersections, which is convenient for numbering 1. N. Bessie started at intersection 1, and her friend (destination) was at intersection N, seeking a short circuit from 1 to N.
The second shortest path can share the road with any shortest path or retreat, even if the same road or intersection is used many times. The second shortest path is the shortest path that is longer than the shortest path (that is, if there are two or more shortest paths, the second shortest path is the path that is longer than the shortest path but not longer than any other path).
Analysis: The maximum number of points is 5000 and the number of edges is 100000. As you can imagine, the picture is very large. The shortest optimal algorithm is SPFA. If the number of edges is less than N*N, consider using adjacency table to store the graph, two-way road, two-way road.

void serve(int a,int b,int c){
    u[k]=a,v[k]=b,w[k]=c;/*Two-way road adjacency table storage method*/
    next[k]=first[a];
    first[a]=k;
    k++;
}

Note: Arrays are opened twice as large as edges.
Find the second short circuit, the shortest path once from vertex 1, and the shortest path once from vertex N.

The second short circuit can be expressed as dis1 [u [i] + dis2 [v [i] + W [i] + dis1 [u [i] + dis2 [v [i] + W [i] + W [i] + dis1 [u [i] + dis2 [v [i] + W [i], but the distance should be greater than the shortest one.

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int v[200100],w[200100],u[200100];
int dis1[200100],dis2[200100];
int book[200100];
int first[200100],next[200100];
int n,m,k;
void serve(int a,int b,int c){
    u[k]=a,v[k]=b,w[k]=c;/*Two-way road adjacency table storage method*/
    next[k]=first[a];
    first[a]=k;
    k++;
}
void SPFA(int x,int *dis){
    memset(book,0,sizeof(book));
    queue<int>Q1;
    Q1.push(x);
    dis[x]=0;
    book[x]=1;
    while(!Q1.empty()){
        int u=Q1.front();
        Q1.pop();
        book[u]=0;
        for(int j=first[u]; j!=-1; j=next[j])//Can relaxation be done through this edge?
            if(dis[v[j]]>dis[u]+w[j]){
                dis[v[j]]=dis[u]+w[j];//Update first, then decide whether to join the queue
                if(book[v[j]]==0){
                    book[v[j]]=1;
                    Q1.push(v[j]);
                }
            }
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        k=0;
        memset(first,-1,sizeof(first));
        memset(dis1,INF,sizeof(dis1));
        memset(dis2,INF,sizeof(dis2));
        for(int i=0; i<m; i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            serve(a,b,c);
            serve(b,a,c);
        }
        SPFA(1,dis1);
        SPFA(n,dis2);
        int mi=INF;
        for(int i=1; i<=n; i++){
            for(int j=first[i]; j!=-1; j=next[j]){
                int sum=dis1[i]+dis2[v[j]]+w[j];
                if(sum>dis1[n]&&sum<mi)
                    mi=sum;
            }
        }
        printf("%d\n",mi);

    }
    return 0;
}