Src/Graph/ShortestPath/WeightedShortestPathTree.hpp

• View this file on GitHub
• Last update: 2023-12-14 22:32:29+09:00
• Include: #include "Src/Graph/ShortestPath/WeightedShortestPathTree.hpp"

Depends on

• Src/Graph/ShortestPath/Edge.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Src/Graph/ShortestPath/Dijkstra.hpp

Verified with

• AOJ2872 最短距離を伸ばすえびちゃん (Test/AOJ/2872.test.cpp)
• Test/LC/shortest_path.test.cpp
• Test/Manual/abc252_e.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "./Edge.hpp"

#include <algorithm>
#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

namespace internal {

template <class Weight>
class WeightedShortestPathTree {
public:
    static_assert(std::is_unsigned_v<Weight>, "Dijkstra's Algorithm only be work well by unsigned weight");
    using E = WeightedEdge<Weight>;
    static constexpr u32 invalid() noexcept {
        return E::invalid();
    }
private:
    static constexpr u32 INVALID{E::invalid()};
    usize n_;
    u32 root_;
    std::vector<E> tree_;
    std::vector<Weight> dist_;
public:
    WeightedShortestPathTree() = default;
    WeightedShortestPathTree(u32 n, u32 root) 
        : n_{n}, root_{root}, tree_(n), dist_(n, static_cast<Weight>(-1)) {
        assert(root < n);
        tree_.shrink_to_fit();
        dist_.shrink_to_fit();
        dist_[root] = Weight{};
    }

    inline usize size() const noexcept {
        return n_;
    }
    inline u32 root() const noexcept {
        return root_;
    }
    inline u32 parent(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].parent;
    }
    inline u32 id(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].id;
    }
    inline bool connect(u32 v) const noexcept {
        assert(v < size());
        return v == root_ or tree_[v].exist();
    }
    inline const Weight& dist(u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    const Weight& operator[](u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    bool relax(u32 from, u32 to, const Weight& weight, u32 id) {
        if (dist_[to] > dist_[from] + weight) {
            dist_[to] = dist_[from] + weight;
            tree_[to].parent = from;
            tree_[to].id = id;
            return true;
        }
        return false;
    }

    std::vector<u32> pathV(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<u32> res(1);
        res[0] = v;
        while (parent(v) != invalid()) {
            v = parent(v);
            res.emplace_back(v);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    std::vector<E> pathE(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<E> res;
        while (v != root()) {
            res.emplace_back(tree_[v]);
            v = parent(v);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
};

} // namespace internal

} // namespace zawa

#line 2 "Src/Graph/ShortestPath/WeightedShortestPathTree.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Graph/ShortestPath/Edge.hpp"

#line 4 "Src/Graph/ShortestPath/Edge.hpp"

namespace zawa {

namespace internal {

class Edge {
protected:
    static constexpr u32 INVALID{static_cast<u32>(-1)};
public:
    u32 parent{INVALID}; 
    u32 id{INVALID};
    Edge() = default;
    Edge(u32 parent, u32 id) : parent{parent}, id{id} {}
    Edge& operator=(const Edge& edge) {
        parent = edge.parent;
        id = edge.id;
        return *this;
    }
    inline bool exist() const noexcept {
        return parent != INVALID;
    }
    static constexpr u32 invalid() noexcept {
        return INVALID; 
    }
};

template <class Weight>
class WeightedEdge : public Edge {
public:
    Weight weight{INVALID};
    WeightedEdge() = default;
    WeightedEdge(u32 parent, const Weight& weight, u32 id)
        : Edge{parent, id}, weight{weight} {}

    WeightedEdge& operator=(const WeightedEdge& edge) {
        parent = edge.parent;
        id = edge.id;
        weight = edge.weight;
        return *this;
    }

};

} // namespace internal

} // namespace zawa
#line 5 "Src/Graph/ShortestPath/WeightedShortestPathTree.hpp"

#include <algorithm>
#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

namespace internal {

template <class Weight>
class WeightedShortestPathTree {
public:
    static_assert(std::is_unsigned_v<Weight>, "Dijkstra's Algorithm only be work well by unsigned weight");
    using E = WeightedEdge<Weight>;
    static constexpr u32 invalid() noexcept {
        return E::invalid();
    }
private:
    static constexpr u32 INVALID{E::invalid()};
    usize n_;
    u32 root_;
    std::vector<E> tree_;
    std::vector<Weight> dist_;
public:
    WeightedShortestPathTree() = default;
    WeightedShortestPathTree(u32 n, u32 root) 
        : n_{n}, root_{root}, tree_(n), dist_(n, static_cast<Weight>(-1)) {
        assert(root < n);
        tree_.shrink_to_fit();
        dist_.shrink_to_fit();
        dist_[root] = Weight{};
    }

    inline usize size() const noexcept {
        return n_;
    }
    inline u32 root() const noexcept {
        return root_;
    }
    inline u32 parent(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].parent;
    }
    inline u32 id(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].id;
    }
    inline bool connect(u32 v) const noexcept {
        assert(v < size());
        return v == root_ or tree_[v].exist();
    }
    inline const Weight& dist(u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    const Weight& operator[](u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    bool relax(u32 from, u32 to, const Weight& weight, u32 id) {
        if (dist_[to] > dist_[from] + weight) {
            dist_[to] = dist_[from] + weight;
            tree_[to].parent = from;
            tree_[to].id = id;
            return true;
        }
        return false;
    }

    std::vector<u32> pathV(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<u32> res(1);
        res[0] = v;
        while (parent(v) != invalid()) {
            v = parent(v);
            res.emplace_back(v);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    std::vector<E> pathE(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<E> res;
        while (v != root()) {
            res.emplace_back(tree_[v]);
            v = parent(v);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
};

} // namespace internal

} // namespace zawa

Back to top page