#include "shortest-path/dijkstra-with-restore.hpp"
#pragma once #include "../data-structure/radix-heap.hpp" #include "../graph/graph-template.hpp" // unreachable -> {-1, -1} template <typename T> vector<pair<T, int>> dijkstra_restore(WeightedGraph<T> &g, int start = 0) { int N = (int)g.size(); using P = pair<T, int>; vector<P> d(N, P{-1, -1}); RadixHeap<T, int> Q; d[start].first = 0; Q.push(0, start); while (!Q.empty()) { auto p = Q.pop(); int cur = p.second; T dc = d[cur].first; if (dc < T(p.first)) continue; for (auto dst : g[cur]) { if (d[dst].first == T(-1) || dc + dst.cost < d[dst].first) { d[dst] = P{dc + dst.cost, cur}; Q.push(dc + dst.cost, dst); } } } return d; } /* * @brief ダイクストラ法(復元付き) **/
#line 2 "shortest-path/dijkstra-with-restore.hpp" #line 2 "data-structure/radix-heap.hpp" template <typename Key, typename Val> struct RadixHeap { using uint = typename make_unsigned<Key>::type; static constexpr int bit = sizeof(Key) * 8; array<vector<pair<uint, Val> >, bit + 1> vs; array<uint, bit + 1> ms; int s; uint last; RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); } bool empty() const { return s == 0; } int size() const { return s; } __attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const { return 64 - _lzcnt_u64(a); } void push(const uint &key, const Val &val) { s++; uint64_t b = getbit(key ^ last); vs[b].emplace_back(key, val); ms[b] = min(key, ms[b]); } pair<uint, Val> pop() { if (ms[0] == uint(-1)) { int idx = 1; while (ms[idx] == uint(-1)) idx++; last = ms[idx]; for (auto &p : vs[idx]) { uint64_t b = getbit(p.first ^ last); vs[b].emplace_back(p); ms[b] = min(p.first, ms[b]); } vs[idx].clear(); ms[idx] = uint(-1); } --s; auto res = vs[0].back(); vs[0].pop_back(); if (vs[0].empty()) ms[0] = uint(-1); return res; } }; /** * @brief Radix Heap * @docs docs/data-structure/radix-heap.md */ #line 2 "graph/graph-template.hpp" template <typename T> struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnweightedGraph = vector<vector<int>>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template <typename T> WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph<T> g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template <typename T> Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges<T> es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template <typename T> vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector<vector<T>> d(N, vector<T>(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ #line 7 "shortest-path/dijkstra-with-restore.hpp" // unreachable -> {-1, -1} template <typename T> vector<pair<T, int>> dijkstra_restore(WeightedGraph<T> &g, int start = 0) { int N = (int)g.size(); using P = pair<T, int>; vector<P> d(N, P{-1, -1}); RadixHeap<T, int> Q; d[start].first = 0; Q.push(0, start); while (!Q.empty()) { auto p = Q.pop(); int cur = p.second; T dc = d[cur].first; if (dc < T(p.first)) continue; for (auto dst : g[cur]) { if (d[dst].first == T(-1) || dc + dst.cost < d[dst].first) { d[dst] = P{dc + dst.cost, cur}; Q.push(dc + dst.cost, dst); } } } return d; } /* * @brief ダイクストラ法(復元付き) **/