Dijkstra seeking secondary short circuit (easy to understand)

step
1. Find the shortest path from the starting point to each point and use dis1 Write down the array ;
2. Find the shortest path at each point and use dis2 Write down the array ;
3. Access each edge （ If it is an undirected graph, it needs to traverse the given number of edges *2）, use u Indicates the starting point of this edge ,v Indicates the end of this side ,w Weight representation , use k Write down the starting point to u The shortest path plus v The shortest path to the destination plus w;
4. Compare k and dis1[ t ] Size , If k > dis1[ t ], Just like ans Compare , If it is less than ans, Update ans The value of is k;
5. A short circuit is ans;

Code ：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=100005;
int t;
ll n,m,k;
ll u[N],v[N],w[N];
ll Min;
bool vis[N];
ll a[N];
ll dis[N],dis1[N],dis2[N];
struct node {
    
    ll to,dis;
    node(ll a,ll b){
    to=a;dis=b;}
    friend bool operator <(node a,node b) {
    
        return a.dis > b.dis;
    }
};
struct Edge {
    
    ll to,cost,next;
}E[N*5];
ll head[N*5],tot;
void add(ll from,ll to,ll v) {
    
    E[tot].to=to;
    E[tot].cost=v;
    E[tot].next=head[from];
    head[from]=tot++;
}
void init() {
    
    memset(dis1,INF,sizeof(dis1));
    memset(dis2,INF,sizeof(dis2));
    memset(head,-1,sizeof(head));
    tot=0;
}
priority_queue<struct node>que;
void dijkstra(ll s) {
    
    memset(vis,false,sizeof(vis));
    memset(dis,INF,sizeof(dis));
    que.push(node(s,0));
    dis[s]=0;
    while(!que.empty()) {
    
        node now=que.top();
        que.pop();
        if(vis[now.to]) continue;
        vis[now.to]=true;
        for(ll i=head[now.to];~i;i=E[i].next) {
    
            ll to=E[i].to;
            ll costlen=E[i].cost+dis[now.to];
            if(dis[to] > costlen) {
    
                dis[to]=costlen;
                if(!vis[to])
                    que.push(node(to,costlen));
            }
        }
    }
}
int main() {
    
    while(~scanf("%lld %lld",&n,&m)) {
    
        init();
        for(ll i=1;i<=m;i++) {
    
            scanf("%lld %lld %lld",&u[i],&v[i],&w[i]);
            u[i+n]=v[i];
            v[i+n]=u[i];
            w[i+n]=w[i];
            add(u[i],v[i],w[i]);
            add(v[i],u[i],w[i]);
        }
        scanf("%lld",&k);
        dijkstra(1);
        for(ll i=1;i<=n;i++) dis1[i]=dis[i];
        dijkstra(n);
        for(ll i=1;i<=n;i++) dis2[i]=dis[i];
        Min=INF;
        for(ll i=1;i<=2*m;i++) {
    
            ll x=u[i],y=v[i],z=w[i];
            ll va=dis1[x]+dis2[y]+z;
            if(va>dis1[n] && va<Min) Min=va;
        }
        printf("%d\n",k==1?Min:dis1[n]);
    }
    return 0;
}