library/graph/shortest_path/Dial.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/graph/shortest_path/Dial.hpp"

Depends on

Verified with

test/AOJ/ALDS1_12_B.test.cpp

Code

#pragma once
#include "library/graph/WeightedGraph.hpp"
template <typename WG, typename T = typename WG::weight_type>
std::pair<std::vector<T>, std::vector<int>> dial(const WG &g, int s = 0) {
    assert(g.is_prepared());
    std::vector<T> d(g.n, -1);
    std::vector<int> pre(g.n, -1);
    std::vector<bool> used(g.n, false);

    T K = 0, rem = 0;
    for (const auto &e : g.edges)
        K = std::max(K, e.weight);
    std::vector<std::queue<int>> que(K + 1);
    auto cmp = [&](T a, T b) {
        if (a == rem || b == rem)
            return b == rem;
        if ((a < rem) ^ (b < rem))
            return a < rem;
        return a > b;
    };
    std::priority_queue<T, std::vector<T>, decltype(cmp)> nxt{cmp};

    d[s] = 0;
    que[0].push(0);
    nxt.push(0);

    while (nxt.size()) {
        rem = nxt.top();
        nxt.pop();
        auto &Q = que[rem];
        while (Q.size()) {
            int v = Q.front();
            Q.pop();
            if (used[v])
                continue;
            used[v] = true;
            for (const auto &e : g[v]) {
                if (d[e.to] == -1 || d[e.to] > d[v] + e.weight) {
                    d[e.to] = d[v] + e.weight;
                    pre[e.to] = v;
                    T x = rem + e.weight;
                    if (x >= K + 1)
                        x -= K + 1;
                    if (!que[x].size())
                        nxt.push(x);
                    que[x].push(e.to);
                }
            }
        }
    }
    return {d, pre};
}

#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
    WeightedEdge() = default;
    WeightedEdge(int from, int to, T weight)
        : from(from), to(to), weight(weight) {}
    int from, to;
    T weight;
    operator int() const { return to; }
};

template <typename T> struct WeightedGraph {
    int n;
    using weight_type = T;
    using edge_type = WeightedEdge<T>;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        WeightedGraph *g;
        int l, r;

      public:
        OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const WeightedGraph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
            : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
    WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to, T weight) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to, weight);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v, T weight) {
        add_arc(u, v, weight);
        add_arc(v, u, weight);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            T weight;
            std::cin >> weight;
            if (directed)
                add_arc(u, v, weight);
            else
                add_edge(u, v, weight);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __DEBUG
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << "(" << edges[i].to << "," << edges[i].weight
                          << ")";
            std::cerr << "\n";
        }
    }
};
#line 3 "library/graph/shortest_path/Dial.hpp"
template <typename WG, typename T = typename WG::weight_type>
std::pair<std::vector<T>, std::vector<int>> dial(const WG &g, int s = 0) {
    assert(g.is_prepared());
    std::vector<T> d(g.n, -1);
    std::vector<int> pre(g.n, -1);
    std::vector<bool> used(g.n, false);

    T K = 0, rem = 0;
    for (const auto &e : g.edges)
        K = std::max(K, e.weight);
    std::vector<std::queue<int>> que(K + 1);
    auto cmp = [&](T a, T b) {
        if (a == rem || b == rem)
            return b == rem;
        if ((a < rem) ^ (b < rem))
            return a < rem;
        return a > b;
    };
    std::priority_queue<T, std::vector<T>, decltype(cmp)> nxt{cmp};

    d[s] = 0;
    que[0].push(0);
    nxt.push(0);

    while (nxt.size()) {
        rem = nxt.top();
        nxt.pop();
        auto &Q = que[rem];
        while (Q.size()) {
            int v = Q.front();
            Q.pop();
            if (used[v])
                continue;
            used[v] = true;
            for (const auto &e : g[v]) {
                if (d[e.to] == -1 || d[e.to] > d[v] + e.weight) {
                    d[e.to] = d[v] + e.weight;
                    pre[e.to] = v;
                    T x = rem + e.weight;
                    if (x >= K + 1)
                        x -= K + 1;
                    if (!que[x].size())
                        nxt.push(x);
                    que[x].push(e.to);
                }
            }
        }
    }
    return {d, pre};
}