关于 __pb_ds 的堆

CaiZi @ 2023-12-17 13:16:42

#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
struct sb{
    int u,w;
    friend int operator <=> (sb x1,sb x2){
        return x1.w-x2.w;
    }
};
int n,m,s,a,b,c,t,k,p[114514];
vector<sb>v[114514];
__gnu_pbds::priority_queue<sb,greater<sb>,rc_binomial_heap_tag>q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s;
    fill(p+1,p+1+n,1145141919);
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        v[a].push_back(sb{b,c});
    }
    q.push(sb{s,0});
    p[s]=0;
    while(!q.empty()){
        t=q.top().u;
        k=q.top().w;
        q.pop();
        if(k!=p[t]){
            continue;
        }
        for(sb i:v[t]){
            if(k+i.w<p[i.u]){
                p[i.u]=k+i.w;
                q.push(sb{i.u,p[i.u]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<p[i]<<" ";
    }
    return 0;
}

by Him_shu @ 2024-02-05 17:38:16

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e14
#define N 250000
struct info 
{
    int v,w;
    bool operator < (const info& u) const {
        return w > u.w;
    }
};
int n,m,s;
int dis[N],vis[N];
vector<info>a[N];
void Dijkstra(int start)
{
    priority_queue<info>sk;
    for(int i = 1;i <= n;++i) dis[i] = 1e17,vis[i] = false;
    dis[start] = 0;

    sk.push({start,0});
    while(sk.empty() == false) {
        int u = sk.top().v;
        sk.pop();

        if(vis[u] == true) continue;
        else vis[u] = true;

        for(auto e : a[u])
            if(vis[e.v] == false && dis[e.v] > dis[u] + e.w) {
                dis[e.v] = dis[u] + e.w;
                sk.push({e.v,dis[e.v]});
            }
    }
}
signed main(){
    cin>>n>>m>>s;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        a[u].push_back({v,w});
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}