test/radix_heap.test.cpp

• View this file on GitHub
• Last update: 2020-03-11 22:42:07+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja

Depends on

• Radix Heap (data_structure/radix_heap.cpp)
• other/bit_width.cpp
• other/countl_zero.cpp
• other/countr_zero.cpp
• other/fast_ios.cpp
• other/int_alias.cpp

Code

#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";
  }
}

Back to top page