Range Edge Graph
(src/graph/RangeEdgeGraph.hpp)

• View this file on GitHub
• Last update: 2023-02-14 22:43:04+09:00
• Include: #include "src/graph/RangeEdgeGraph.hpp"

概要

区間から区間に辺が伸びるようなグラフ上での最短路を計算する. Segment Treeの構造を利用して頂点数$3n+q$, 辺数$4n+q\log n$のグラフを構成している.

• ‘add_edge(l1, r1, l2, r2, cost)’：$[l1,r1)$から$[l2,r2)$に対して伸びる重み$cost$の辺を追加する.
• ‘build(s)’：$s$を始点にしたときの各点までの最短距離を計算する.

計算量

• ‘add_edge(l1, r1, l2, r2, cost)’：$O(\log n)$
• ‘build(s)’：$O(n+q\log n)\log(n+q)$

参照

区間に辺を張るテクの実装例（Dijkstra法セット）と使用例 - Lorent’s diary

問題例

• The 1st Universal Cup. Stage 3: Poland F. Flower Garden

Code

#pragma once
#include <limits>
#include <queue>
#include <vector>

template <typename T> struct RangeEdgeGraph {
public:
    RangeEdgeGraph(int n) : n(n), G(3 * n) {
        for (int i = 1; i < n; i++) {
            int l = i << 1 | 0, r = i << 1 | 1;
            add_edge(i, l, 0);
            add_edge(i, r, 0);
            add_edge(l + 2 * n, i + 2 * n, 0);
            add_edge(r + 2 * n, i + 2 * n, 0);
        }
    }
    void add_edge(int l1, int r1, int l2, int r2, T cost) {
        int add = G.size();
        G.emplace_back();
        for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
            if (l1 & 1) add_edge((l1++) + 2 * n, add, 0);
            if (r1 & 1) add_edge((--r1) + 2 * n, add, 0);
        }
        for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
            if (l2 & 1) G[add].emplace_back(l2++, cost);
            if (r2 & 1) G[add].emplace_back(--r2, cost);
        }
    }
    std::vector<T> build(int s) {
        std::vector<T> dp(G.size(), std::numeric_limits<T>::max());
        s += n;
        dp[s] = 0;
        std::priority_queue<edge> pq;
        pq.emplace(s, dp[s]);
        while (!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            int v = p.to;
            if (dp[v] < p.cost) continue;
            for (const auto& e : G[v]) {
                int u = e.to;
                if (dp[v] + e.cost < dp[u]) {
                    dp[u] = dp[v] + e.cost;
                    pq.emplace(u, dp[u]);
                }
            }
        }
        std::vector<T> res(dp.begin() + n, dp.begin() + 2 * n);
        return res;
    }

private:
    struct edge {
        int to;
        T cost;
        edge(int to, T cost) : to(to), cost(cost) {}
        bool operator<(const edge& rhs) const { return cost > rhs.cost; }
    };
    int n;
    std::vector<std::vector<edge>> G;
    void add_edge(int u, int v, T cost) { G[(3 * n <= u ? u - 2 * n : u)].emplace_back(v, cost); }
};

#line 2 "src/graph/RangeEdgeGraph.hpp"
#include <limits>
#include <queue>
#include <vector>

template <typename T> struct RangeEdgeGraph {
public:
    RangeEdgeGraph(int n) : n(n), G(3 * n) {
        for (int i = 1; i < n; i++) {
            int l = i << 1 | 0, r = i << 1 | 1;
            add_edge(i, l, 0);
            add_edge(i, r, 0);
            add_edge(l + 2 * n, i + 2 * n, 0);
            add_edge(r + 2 * n, i + 2 * n, 0);
        }
    }
    void add_edge(int l1, int r1, int l2, int r2, T cost) {
        int add = G.size();
        G.emplace_back();
        for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
            if (l1 & 1) add_edge((l1++) + 2 * n, add, 0);
            if (r1 & 1) add_edge((--r1) + 2 * n, add, 0);
        }
        for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
            if (l2 & 1) G[add].emplace_back(l2++, cost);
            if (r2 & 1) G[add].emplace_back(--r2, cost);
        }
    }
    std::vector<T> build(int s) {
        std::vector<T> dp(G.size(), std::numeric_limits<T>::max());
        s += n;
        dp[s] = 0;
        std::priority_queue<edge> pq;
        pq.emplace(s, dp[s]);
        while (!pq.empty()) {
            auto p = pq.top();
            pq.pop();
            int v = p.to;
            if (dp[v] < p.cost) continue;
            for (const auto& e : G[v]) {
                int u = e.to;
                if (dp[v] + e.cost < dp[u]) {
                    dp[u] = dp[v] + e.cost;
                    pq.emplace(u, dp[u]);
                }
            }
        }
        std::vector<T> res(dp.begin() + n, dp.begin() + 2 * n);
        return res;
    }

private:
    struct edge {
        int to;
        T cost;
        edge(int to, T cost) : to(to), cost(cost) {}
        bool operator<(const edge& rhs) const { return cost > rhs.cost; }
    };
    int n;
    std::vector<std::vector<edge>> G;
    void add_edge(int u, int v, T cost) { G[(3 * n <= u ? u - 2 * n : u)].emplace_back(v, cost); }
};

Back to top page