This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub noshi91/Library
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja" #include "data_structure/radix_heap.cpp" #include <iostream> #include <limits> #include <utility> #include <vector> int main() { #include "other/fast_ios.cpp" int n, m, r; std::cin >> n >> m >> r; std::vector<std::vector<std::pair<int, int>>> g(n); for (int i = 0; i != m; i += 1) { int s, t, d; std::cin >> s >> t >> d; g[s].emplace_back(d, t); } constexpr int Inf = std::numeric_limits<int>::max(); std::vector<int> dist(n, Inf); dist[r] = 0; radix_heap<int> heap; int size = 0; heap.push({0, r}); size += 1; while (size != 0) { const auto [c_, v] = heap.pop(); const int c = c_; size -= 1; if (dist[v] < c) continue; for (const auto &[d, u] : g[v]) { if (c + d < dist[u]) { dist[u] = c + d; heap.push({dist[u], u}); size += 1; } } } for (int i = 0; i != n; i += 1) { if (dist[i] < Inf) std::cout << dist[i]; else std::cout << "INF"; std::cout << "\n"; } }
#line 1 "test/radix_heap.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja" #line 2 "other/bit_width.cpp" #line 2 "other/countl_zero.cpp" #line 2 "other/countr_zero.cpp" #line 2 "other/int_alias.cpp" #include <cstddef> #include <cstdint> using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; #line 4 "other/countr_zero.cpp" #include <array> usize countr_zero(u64 x) { if (x == 0) return 64; #ifdef __GNUC__ return __builtin_ctzll(x); #else constexpr std::array<usize, 64> table = { 0, 1, 2, 7, 3, 13, 8, 27, 4, 33, 14, 36, 9, 49, 28, 19, 5, 25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57, 63, 6, 12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56, 62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58}; return table[(x & ~x + 1) * 0x218A7A392DD9ABF >> 58 & 0x3F]; #endif } #line 5 "other/countl_zero.cpp" usize countl_zero(u64 x) { #ifdef __GNUC__ return x == 0 ? 64 : __builtin_clzll(x); #else x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; return 64 - countr_zero(~x); #endif } #line 5 "other/bit_width.cpp" usize bit_width(const u64 x) { return 64 - countl_zero(x); } #line 3 "data_structure/radix_heap.cpp" #include <algorithm> #include <cassert> #include <limits> #include <utility> #include <vector> template <class T> class radix_heap { using V = std::pair<u64, T>; public: using key_type = u64; using mapped_type = T; using value_type = V; private: std::vector<std::vector<V>> u; u64 last; public: radix_heap() : u(), last(0) {} void push(V x) { assert(last <= x.first); const usize i = bit_width(x.first ^ last); if (u.size() <= i) u.resize(i + 1); u[i].push_back(std::move(x)); } V pop() { if (u[0].empty()) { usize i = 1; while (u[i].empty()) i += 1; last = std::numeric_limits<u64>::max(); for (const V &e : u[i]) last = std::min(last, e.first); for (V &e : u[i]) { const usize j = bit_width(e.first ^ last); u[j].push_back(std::move(e)); } u[i].clear(); } V ret = std::move(u[0].back()); u[0].pop_back(); return ret; } }; /** * @brief Radix Heap * @see https://yosupo.hatenablog.com/entry/2015/04/03/224649 */ #line 5 "test/radix_heap.test.cpp" #include <iostream> #line 10 "test/radix_heap.test.cpp" int main() { #line 1 "other/fast_ios.cpp" std::ios::sync_with_stdio(false); std::cin.tie(nullptr); #line 13 "test/radix_heap.test.cpp" int n, m, r; std::cin >> n >> m >> r; std::vector<std::vector<std::pair<int, int>>> g(n); for (int i = 0; i != m; i += 1) { int s, t, d; std::cin >> s >> t >> d; g[s].emplace_back(d, t); } constexpr int Inf = std::numeric_limits<int>::max(); std::vector<int> dist(n, Inf); dist[r] = 0; radix_heap<int> heap; int size = 0; heap.push({0, r}); size += 1; while (size != 0) { const auto [c_, v] = heap.pop(); const int c = c_; size -= 1; if (dist[v] < c) continue; for (const auto &[d, u] : g[v]) { if (c + d < dist[u]) { dist[u] = c + d; heap.push({dist[u], u}); size += 1; } } } for (int i = 0; i != n; i += 1) { if (dist[i] < Inf) std::cout << dist[i]; else std::cout << "INF"; std::cout << "\n"; } }