graph/dijkstra_common.cpp

• View this file on GitHub
• Last update: 2026-03-12 14:17:55+09:00

Required by

• Dijkstra法 (graph/dijkstra.cpp)
• Dijkstra法(Radix Heap) (graph/dijkstra_radix_heap.cpp)
• 経路復元付きDijkstra法 (graph/dijkstra_restore.cpp)

Verified with

• test/aoj0275_dynamic_bitset.test.cpp
• test/aoj0275_static_bitset.test.cpp
• test/aoj_grl_1_a_dijkstra.test.cpp
• test/yosupo_shortest_path.test.cpp
• test/yosupo_shortest_path_radix_heap.test.cpp

Code

#ifndef FIRIEXP_LIBRARY_GRAPH_DIJKSTRA_COMMON_CPP
#define FIRIEXP_LIBRARY_GRAPH_DIJKSTRA_COMMON_CPP

template <typename T>
struct edge {
    int from, to;
    T cost;

    edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
struct DijkstraPriorityQueue {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;

    bool empty() const { return q.empty(); }

    void push(T cost, int v) {
        q.emplace(cost, v);
    }

    pair<T, int> pop() {
        auto res = q.top();
        q.pop();
        return res;
    }
};

template <typename T, class Queue, class OnRelax>
vector<T> dijkstra_internal(int s, const vector<vector<edge<T>>> &G, Queue &Q, OnRelax on_relax) {
    int n = (int)G.size();
    vector<T> dist(n, INF<T>);
    dist[s] = 0;
    Q.push(T(0), s);
    while (!Q.empty()) {
        auto [cost, v] = Q.pop();
        if (dist[v] < cost) continue;
        for (auto &&e : G[v]) {
            T nxt = cost + e.cost;
            if (dist[e.to] <= nxt) continue;
            dist[e.to] = nxt;
            on_relax(v, e);
            Q.push(nxt, e.to);
        }
    }
    return dist;
}

template <typename T, class Queue>
vector<T> dijkstra_internal(int s, const vector<vector<edge<T>>> &G, Queue &Q) {
    return dijkstra_internal(s, G, Q, [](int, const edge<T> &) {});
}

#endif

#line 1 "graph/dijkstra_common.cpp"



template <typename T>
struct edge {
    int from, to;
    T cost;

    edge(int to, T cost) : from(-1), to(to), cost(cost) {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};

template <typename T>
struct DijkstraPriorityQueue {
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;

    bool empty() const { return q.empty(); }

    void push(T cost, int v) {
        q.emplace(cost, v);
    }

    pair<T, int> pop() {
        auto res = q.top();
        q.pop();
        return res;
    }
};

template <typename T, class Queue, class OnRelax>
vector<T> dijkstra_internal(int s, const vector<vector<edge<T>>> &G, Queue &Q, OnRelax on_relax) {
    int n = (int)G.size();
    vector<T> dist(n, INF<T>);
    dist[s] = 0;
    Q.push(T(0), s);
    while (!Q.empty()) {
        auto [cost, v] = Q.pop();
        if (dist[v] < cost) continue;
        for (auto &&e : G[v]) {
            T nxt = cost + e.cost;
            if (dist[e.to] <= nxt) continue;
            dist[e.to] = nxt;
            on_relax(v, e);
            Q.push(nxt, e.to);
        }
    }
    return dist;
}

template <typename T, class Queue>
vector<T> dijkstra_internal(int s, const vector<vector<edge<T>>> &G, Queue &Q) {
    return dijkstra_internal(s, G, Q, [](int, const edge<T> &) {});
}

Back to top page