spfa AcWing 851. SPFA finding the shortest path

spfa AcWing 851. spfa Find the shortest path

Original link

851. spfa Find the shortest path

Algorithm tags

shortest path spfa

Ideas

Find the shortest path algorithm summary
This picture is taken from this video
spfa The algorithm is right Bellman_ford Optimization of algorithm
Bellman_ford The algorithm will traverse all the edges , But there are a lot of edge traversals, which actually makes no sense , We only need to traverse the edges connected by the points whose distance to the source becomes smaller , Only when the precursor node of a point is updated , This node will be updated ; So with this in mind , We will create a queue, each time we join the node whose distance is updated .

The figure is extracted from the solution to the problem

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
int h[N], e[N], ne[N], w[N], idx;
int dis[N];
bool st[N];
int n,m;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void add(int a, int b, int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int sp(){
    memset(dis, 0x3f, sizeof dis);
    dis[0]=1;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size()){
        int t=q.front();
        q.pop();
        //  After being taken out of the queue, the node st Marked as false, After the delegate, if the node is updated, it can join the queue again 
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>dis[t]+w[i]){
                dis[j]=dis[t]+w[i];
                if(!st[j]){//  The node that has been added to the queue , No need to join the queue again , Even if an update occurs, only the value can be updated , Repeated addition reduces efficiency 
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return dis[n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(h, -1, sizeof h);
    n=read(), m=read();
    while(m--){
        int x=read(), y=read(), z=read();
        add(x, y, z);
    }
    if(sp()==0x3f3f3f3f){
        puts("impossible");
    }else{
        printf("%lld\n", sp());
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support