Dijkstra AcWing 850. Dijkstra finding the shortest circuit II

Dijkstra AcWing 850. Dijkstra Find the shortest path II

Original link

AcWing 850. Dijkstra Find the shortest path II

Algorithm tags

shortest path Dijkstra

Ideas

The picture is extracted from the solution of the question

The picture is extracted from the solution of the question

Code

#include<bits/stdc++.h>
#define x first
#define y second 
using namespace std;
typedef pair<int, int>PII;
const int N = 150005;
int n,m;
int dist[N];
//  Sparse graphs are stored in adjacency tables 
int h[N], w[N], e[N], ne[N], idx;
bool st[N];
void add(int a,int b,int c){
	//  It doesn't matter if there are heavy edges , hypothesis 1->2 Weighted as 2 and 3 The edge of , Then traverse to point 1 When 2 The distance of point No. will be updated twice and put into the heap 
    //  In this way, there will be many redundant points in the heap , But the minimum value will pop up when it pops up 2+x（x For the shortest path determined before ）,
    //  Tagged st by true, So next time it pops up 3+x Meeting continue It doesn't go down .
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dij(){
    memset(dist, 0x3f , sizeof dist);
    dist[1] = 0;
    //  here heap Why do you want to save pair Well , First, small root piles are arranged according to distance , So there's a variable called distance ,
    //  Secondly, when taking it out of the heap, you should know which point this point is , Otherwise, how to update the adjacency point ？ So the second variable needs to be saved .
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,1});
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.y,dis = t.x;
        if(st[ver]){
            continue;
        }
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i]){
        	// i Just a subscript ,e What is stored in the is i The point corresponding to this subscript .
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f){
        return -1;
    }
    return dist[n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    memset(h, -1, sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dij()<<"\n";
}

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