CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: cp-algo/graph/shortest_path.hpp

Depends on

Verified with

Code

#ifndef CP_ALGO_GRAPH_SHORTEST_PATH_HPP
#define CP_ALGO_GRAPH_SHORTEST_PATH_HPP
#include "base.hpp"
#include <algorithm>
#include <queue>
namespace cp_algo::graph {
    template<type _, weighted_edge_type edge_t>
    auto dijkstra(graph<_, edge_t> const& g, int s) {
        static constexpr uint64_t inf = 1e18;
        std::vector<uint64_t> dist(g.n(), inf);
        std::vector<std::pair<node_index, edge_index>> pre(g.n());
        using que_t = std::pair<uint64_t, node_index>;
        std::priority_queue<que_t, std::vector<que_t>, std::greater<>> que;
        dist[s] = 0;
        que.push({0, s});
        while(!empty(que)) {
            auto [dv, v] = que.top();
            que.pop();
            if(dv != dist[v]) {
                continue;
            }
            g.call_adjacent(v, [&](auto e) {
                node_index u = g.edge(e).to;
                auto w = g.edge(e).w;
                if(dist[v] + w < dist[u]) {
                    pre[u] = {v, e};
                    dist[u] = dist[v] + w;
                    que.push({dist[u], u});
                }
            });
        }
        return std::pair{dist, pre};
    }

    template<type _, weighted_edge_type edge_t>
    auto shortest_path(graph<_, edge_t> const& g, int s, int t) {
        static constexpr uint64_t inf = 1e18;
        auto [dist, pre] = dijkstra(g, s);
        std::vector<std::pair<node_index, edge_index>> path;
        int64_t d = dist[t] == inf ? -1 : dist[t];
        while(d != -1 && t != s) {
            path.push_back(pre[t]);
            t = pre[t].first;
        }
        std::ranges::reverse(path);
        return std::pair{d, path};
    }
}
#endif // CP_ALGO_GRAPH_SHORTEST_PATH_HPP
#line 1 "cp-algo/graph/shortest_path.hpp"


#line 1 "cp-algo/graph/base.hpp"


#line 1 "cp-algo/graph/edge_types.hpp"


#include <iostream>
#include <cstdint>
namespace cp_algo::graph {
    using node_index = int;
    struct edge_base {
        node_index to;

        edge_base() {}
        edge_base(node_index v): to(v) {}

        static auto read(node_index v0 = 0) {
            node_index u, v;
            std::cin >> u >> v;
            return std::pair{u - v0, edge_base(v - v0)};
        }

        edge_base backedge(int from) const {
            return {from};
        }
    };

    struct weighted_edge: edge_base {
        int64_t w;

        weighted_edge() {}
        weighted_edge(node_index v, int64_t w): edge_base(v), w(w) {}

        static auto read(node_index v0 = 0) {
            node_index u, v;
            int64_t w;
            std::cin >> u >> v >> w;
            return std::pair{u - v0, weighted_edge{v - v0, w}};
        }

        weighted_edge backedge(node_index from) const {
            return {from, w};
        }
    };

    template<typename edge>
    concept edge_type = std::is_base_of_v<edge_base, edge>;
    template<typename edge>
    concept weighted_edge_type = std::is_base_of_v<weighted_edge, edge>;
}

#line 1 "cp-algo/structures/stack_union.hpp"


#include <cstddef>
#include <vector>
namespace cp_algo::structures {
    template<class datatype>
    struct stack_union {
        stack_union(int n = 0): head(n), next(1), data(1) {}

        void push(int v, datatype const& vdata) {
            next.push_back(head[v]);
            head[v] = (int)std::size(next) - 1;
            data.push_back(vdata);
        }
        template<typename... Args>
        void emplace(int v, Args&&... vdata) {
            next.push_back(head[v]);
            head[v] = size(next) - 1;
            data.emplace_back(std::forward<Args...>(vdata...));
        }

        void reserve(int m) {
            data.reserve(m);
            next.reserve(m);
        }

        size_t size() const {return std::size(head);}
        size_t nodes() const {return std::size(data);}

        std::vector<int> head, next;
        std::vector<datatype> data;
    };
}

#line 5 "cp-algo/graph/base.hpp"
#include <ranges>
#line 7 "cp-algo/graph/base.hpp"
namespace cp_algo::graph {
    using edge_index = int;
    enum type {directed = 0, undirected = 1};
    template<type _undirected, edge_type edge_t = edge_base>
    struct graph {
        static constexpr bool undirected = _undirected;
        graph(int n, int v0 = 0): v0(v0), adj(n) {}

        void add_edge(node_index u, edge_t e) {
            adj.push(u, (edge_index)size(edges));
            edges.push_back(e);
            if constexpr (undirected) {
                adj.push(e.to, (edge_index)size(edges));
            }
            edges.push_back(e.backedge(u));
        }
        void read_edges(node_index m) {
            adj.reserve(m);
            for(edge_index i = 0; i < m; i++) {
                auto [u, e] = edge_t::read(v0);
                add_edge(u, e);
            }
        }
        void call_adjacent(node_index v, auto &&callback, auto &&terminate) const {
            for(int sv = adj.head[v]; sv && !terminate(); sv = adj.next[sv]) {
                callback(adj.data[sv]);
            }
        }
        void call_adjacent(node_index v, auto &&callback) const {
            call_adjacent(v, callback, [](){return false;});
        }
        void call_edges(auto &&callback) const {
            for(edge_index e: edges_view()) {
                callback(e);
            }
        }
        auto nodes_view() const {
            return std::views::iota(0, n());
        }
        auto edges_view() const {
            return std::views::iota(0, 2 * m()) | std::views::filter(
                [](edge_index e) {return !(e % 2);}
            );
        }
        auto const& incidence_lists() const {return adj;}
        edge_t const& edge(edge_index e) const {return edges[e];}
        node_index n() const {return (node_index)adj.size();}
        edge_index m() const {return (edge_index)size(edges) / 2;}
    private:
        node_index v0;
        std::vector<edge_t> edges;
        structures::stack_union<edge_index> adj;
    };
}

#line 4 "cp-algo/graph/shortest_path.hpp"
#include <algorithm>
#include <queue>
namespace cp_algo::graph {
    template<type _, weighted_edge_type edge_t>
    auto dijkstra(graph<_, edge_t> const& g, int s) {
        static constexpr uint64_t inf = 1e18;
        std::vector<uint64_t> dist(g.n(), inf);
        std::vector<std::pair<node_index, edge_index>> pre(g.n());
        using que_t = std::pair<uint64_t, node_index>;
        std::priority_queue<que_t, std::vector<que_t>, std::greater<>> que;
        dist[s] = 0;
        que.push({0, s});
        while(!empty(que)) {
            auto [dv, v] = que.top();
            que.pop();
            if(dv != dist[v]) {
                continue;
            }
            g.call_adjacent(v, [&](auto e) {
                node_index u = g.edge(e).to;
                auto w = g.edge(e).w;
                if(dist[v] + w < dist[u]) {
                    pre[u] = {v, e};
                    dist[u] = dist[v] + w;
                    que.push({dist[u], u});
                }
            });
        }
        return std::pair{dist, pre};
    }

    template<type _, weighted_edge_type edge_t>
    auto shortest_path(graph<_, edge_t> const& g, int s, int t) {
        static constexpr uint64_t inf = 1e18;
        auto [dist, pre] = dijkstra(g, s);
        std::vector<std::pair<node_index, edge_index>> path;
        int64_t d = dist[t] == inf ? -1 : dist[t];
        while(d != -1 && t != s) {
            path.push_back(pre[t]);
            t = pre[t].first;
        }
        std::ranges::reverse(path);
        return std::pair{d, path};
    }
}

Back to top page