graph/dijkstra.hpp

View this file on GitHub
Last update: 2024-04-16 00:47:17+09:00
Include: #include "graph/dijkstra.hpp"

Code

vector<ll> dijkstra(Graph& G, int s){
    int n = G.size();
    vector<ll> dist(n, LLINF);
    dist[s] = 0;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    pq.emplace(0, s);
    while(!pq.empty()) {
        auto [nowCost, now] = pq.top(); pq.pop();
        if(dist[now] < nowCost) continue;
        for(auto to: G[now]) {
            if(chmin(dist[to], nowCost + 1)) pq.emplace(nowCost + 1, to);
        }
    }
    return dist;
}

#line 1 "graph/dijkstra.hpp"
vector<ll> dijkstra(Graph& G, int s){
    int n = G.size();
    vector<ll> dist(n, LLINF);
    dist[s] = 0;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    pq.emplace(0, s);
    while(!pq.empty()) {
        auto [nowCost, now] = pq.top(); pq.pop();
        if(dist[now] < nowCost) continue;
        for(auto to: G[now]) {
            if(chmin(dist[to], nowCost + 1)) pq.emplace(nowCost + 1, to);
        }
    }
    return dist;
}