C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/区間に辺を張るテク * * verification-helper: IGNORE * verification-helper: PROBLEM https://codeforces.com/problemset/problem/786/B */ #include <iostream> #include <vector> #include "emthrm/graph/noshi_graph.hpp" #include "emthrm/graph/shortest_path/dijkstra.hpp" int main() { int n, q, s; std::cin >> n >> q >> s; --s; emthrm::NoshiGraph<long long> graph(n); while (q--) { int t, v; std::cin >> t >> v; --v; if (t == 1) { int u, w; std::cin >> u >> w; --u; graph.add_edge(v, u, w); } else { int l, r, w; std::cin >> l >> r >> w; --l; --r; if (t == 2) { graph.add_edge(v, v + 1, l, r + 1, w); } else if (t == 3) { graph.add_edge(l, r + 1, v, v + 1, w); } } } emthrm::Dijkstra<long long> dijkstra(graph.graph); const std::vector<long long> ans = dijkstra.build(s); for (int i = 0; i < n; ++i) { std::cout << (ans[i] == dijkstra.inf ? -1 : ans[i]) << " \n"[i + 1 == n]; } return 0; }
#line 1 "test/graph/noshi_graph.test.cpp" /* * @title グラフ/区間に辺を張るテク * * verification-helper: IGNORE * verification-helper: PROBLEM https://codeforces.com/problemset/problem/786/B */ #include <iostream> #include <vector> #line 1 "include/emthrm/graph/noshi_graph.hpp" #include <bit> #line 6 "include/emthrm/graph/noshi_graph.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 8 "include/emthrm/graph/noshi_graph.hpp" namespace emthrm { template <typename CostType> struct NoshiGraph { std::vector<std::vector<Edge<CostType>>> graph; explicit NoshiGraph(const int n) : p2(std::bit_ceil(static_cast<unsigned int>(n))) { const int dbl = p2 << 1, hlf = p2 >> 1; graph.resize(dbl + p2); for (int i = 1; i < hlf; ++i) { add_edge(i + p2, (i << 1) + p2); add_edge(i + p2, (i << 1) + 1 + p2); add_edge((i << 1) + dbl, i + dbl); add_edge((i << 1) + 1 + dbl, i + dbl); } for (int src = p2 + hlf, dst = 0; dst < p2; ++src, dst += 2) { add_edge(src, dst); add_edge(src, dst + 1); } for (int src = 0, dst = dbl + hlf; src < p2; src += 2, ++dst) { add_edge(src, dst); add_edge(src + 1, dst); } } void add_edge(const int src, const int dst, const CostType cost = 0) { graph[src].emplace_back(src, dst, cost); } void add_edge(int src_l, int src_r, int dst_l, int dst_r, const CostType cost) { if (src_r <= src_l || dst_r <= dst_l) [[unlikely]] return; const int src_id = graph.size(), dst_id = src_id + 1; graph.emplace_back(); graph.emplace_back(); if ((dst_l += p2) & 1) add_edge(dst_id, dst_l++ - p2); if ((dst_r += p2) & 1) add_edge(dst_id, --dst_r - p2); for (dst_l >>= 1, dst_r >>= 1; dst_l < dst_r; dst_l >>= 1, dst_r >>= 1) { if (dst_l & 1) add_edge(dst_id, dst_l++ + p2); if (dst_r & 1) add_edge(dst_id, --dst_r + p2); } add_edge(src_id, dst_id, cost); if ((src_l += p2) & 1) add_edge(src_l++ - p2, src_id); if ((src_r += p2) & 1) add_edge(--src_r - p2, src_id); for (src_l >>= 1, src_r >>= 1; src_l < src_r; src_l >>= 1, src_r >>= 1) { if (src_l & 1) add_edge(src_l++ + (p2 << 1), src_id); if (src_r & 1) add_edge(--src_r + (p2 << 1), src_id); } } private: const int p2; }; } // namespace emthrm #line 1 "include/emthrm/graph/shortest_path/dijkstra.hpp" #include <algorithm> #include <cassert> #include <functional> #include <limits> #include <queue> #include <utility> #line 11 "include/emthrm/graph/shortest_path/dijkstra.hpp" #line 1 "include/emthrm/graph/edge.hpp" /** * @title 辺 */ #ifndef EMTHRM_GRAPH_EDGE_HPP_ #define EMTHRM_GRAPH_EDGE_HPP_ #include <compare> namespace emthrm { template <typename CostType> struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; } // namespace emthrm #endif // EMTHRM_GRAPH_EDGE_HPP_ #line 13 "include/emthrm/graph/shortest_path/dijkstra.hpp" namespace emthrm { template <typename CostType> struct Dijkstra { const CostType inf; Dijkstra(const std::vector<std::vector<Edge<CostType>>>& graph, const CostType inf = std::numeric_limits<CostType>::max()) : inf(inf), is_built(false), graph(graph) {} std::vector<CostType> build(const int s) { is_built = true; const int n = graph.size(); std::vector<CostType> dist(n, inf); dist[s] = 0; prev.assign(n, -1); std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> que; que.emplace(0, s); while (!que.empty()) { const auto [d, ver] = que.top(); que.pop(); if (d > dist[ver]) continue; for (const Edge<CostType>& e : graph[ver]) { if (dist[ver] + e.cost < dist[e.dst]) { dist[e.dst] = dist[ver] + e.cost; prev[e.dst] = ver; que.emplace(dist[e.dst], e.dst); } } } return dist; } std::vector<int> build_path(int t) const { assert(is_built); std::vector<int> res; for (; t != -1; t = prev[t]) { res.emplace_back(t); } std::reverse(res.begin(), res.end()); return res; } private: bool is_built; std::vector<int> prev; std::vector<std::vector<Edge<CostType>>> graph; }; } // namespace emthrm #line 13 "test/graph/noshi_graph.test.cpp" int main() { int n, q, s; std::cin >> n >> q >> s; --s; emthrm::NoshiGraph<long long> graph(n); while (q--) { int t, v; std::cin >> t >> v; --v; if (t == 1) { int u, w; std::cin >> u >> w; --u; graph.add_edge(v, u, w); } else { int l, r, w; std::cin >> l >> r >> w; --l; --r; if (t == 2) { graph.add_edge(v, v + 1, l, r + 1, w); } else if (t == 3) { graph.add_edge(l, r + 1, v, v + 1, w); } } } emthrm::Dijkstra<long long> dijkstra(graph.graph); const std::vector<long long> ans = dijkstra.build(s); for (int i = 0; i < n; ++i) { std::cout << (ans[i] == dijkstra.inf ? -1 : ans[i]) << " \n"[i + 1 == n]; } return 0; }