test/aoj/dijkstra_fibonacci.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A"
#include "include/mtl/fibonacci_heap.hpp"
#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 11e8;

int main() {
  int v,e,r; cin>>v>>e>>r;
  vector<pair<int,int>> G[v];
  for (int i = 0; i < e; i++) {
    int s,t,d; cin>>s>>t>>d;
    G[s].emplace_back(t, d);
  }

  vector<int> dist(v, INF);
  FibonacciHeap<int, greater<>> qs(v);
  dist[r] = 0;
  qs.push(r, 0);
  while (!qs.empty()) {
    auto [s, c] = qs.top(); qs.pop();
    assert(c == dist[s]);
    for (auto [t, d] : G[s]) {
      if (dist[t] <= c + d) continue;
      dist[t] = c + d;
      qs.push(t, c + d);
    }
  }
  for (int i = 0; i < v; i++) {
    if (dist[i] != INF) {
      cout << dist[i] << endl;
    } else {
      cout << "INF" << endl;
    }
  }

}

#line 1 "test/aoj/dijkstra_fibonacci.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A"
#line 2 "include/mtl/fibonacci_heap.hpp"
#include <memory>
#include <cassert>
#include <vector>
#include <array>
#include <list>
#include <iostream>

template<typename T, typename Cond = std::less<>>
class FibonacciHeap {
  Cond cond_;

 public:
  struct Node;
  using node_ptr = Node*;
  using const_node_ptr = const Node*;
  struct Node {
    node_ptr next = nullptr;
    node_ptr prev = nullptr;
    node_ptr child = nullptr;
    node_ptr parent = nullptr;
    int deg = 0;
    bool marked = false;
    bool enabled = false;
    std::pair<int, T> value;

    Node() = default;
    void init(int k, T v) {
      next = prev = this;
      child = parent = nullptr;
      deg = 0;
      marked = false;
      enabled = true;
      value = {k, v};
    }
    T priority() const { return value.second; }
    void free() {
      enabled = false;
    }
  };

 private:
  node_ptr root_ = nullptr;
  size_t sz_ = 0;
  std::vector<node_ptr> map_;
  std::vector<Node> container_;
  std::vector<node_ptr> deg_table_;

 public:
  explicit FibonacciHeap(size_t size) : map_(size) {
    container_.reserve(size);
    std::array<size_t,2> tb{1,1};
    int k = 2;
    while (tb[1] < size) {
      auto x = tb[0]+tb[1];
      tb[0] = tb[1];
      tb[1] = x;
      ++k;
    }
    deg_table_.resize(k);
  }

  inline std::pair<int, T> top() const {
    assert(root_ and root_->enabled);
    return root_->value;
  }

  inline std::pair<int, T> get(int key) const {
    assert(map_[key] and map_[key]->enabled);
    return map_[key]->value;
  }

  // Time complexity: O(1)
  void push(int key, T value) {
    if (map_[key] and map_[key]->enabled) {
      update(key, value);
      return;
    }
    if (!map_[key]) {
      container_.emplace_back();
      map_[key] = &container_.back();
    }
    node_ptr node = map_[key];
    node->init(key, value);
    _PushLink(node, &deg_table_[0]);
    if (!root_ or _CompareNodePriority(root_, node))
      root_ = node;
    ++sz_;
  }

  // Time complexity: O(log n)
  void update(int key, T updated_value) {
    if (!map_[key] or !map_[key]->enabled) {
      push(key, updated_value);
      return;
    }
    auto node = map_[key];
    if (!cond_(node->priority(), updated_value)) {
      return;
    }
    node->value.second = updated_value;
    if (node->parent and _CompareNodePriority(node->parent, node)) {
      _Consolidate(node);
    }
    assert(root_);
    if (_CompareNodePriority(root_, node)) {
      root_ = node;
    }
  }

  // Time complexity: O(log n)
  void pop() {
    assert(root_);
    auto r = root_;
    root_ = nullptr;
    _PopLink(r, &deg_table_[r->deg]);
    _ExpandChildren(r);
    _ExtractTop();
    r->free();
    --sz_;
  }

  // Time complexity: O(log n)
  void erase(int key) {
    assert(map_[key] and map_[key]->enabled);
    auto node = map_[key];
    bool needs_extraction = root_ == node;
    if (node->parent) {
      _Consolidate(node);
    }
    assert(!node->parent);
    _PopLink(node, &deg_table_[node->deg]);
    _ExpandChildren(node);
    if (needs_extraction)
      _ExtractTop();
    node->free();
    --sz_;
  }

  size_t size() const { return sz_; }
  bool empty() const { return size() == 0; }
  void clear() {
    root_ = nullptr;
    sz_ = 0;
    map_.fill(nullptr);
    container_.clear();
  }

  void print_for_debug() const {
      for (int k = 0; k < (int)deg_table_.size(); k++) {
        std::cout<<"d="<<k<<std::endl;
        if (deg_table_[k]) {
          std::cout<<"forward"<<std::endl;
          auto r = deg_table_[k];
          do {
            std::cout << r->priority() << ' ' << std::flush;
            r = r->next;
          } while (r != deg_table_[k]);
          std::cout<<std::endl;
          std::cout<<"deg"<<std::endl;
          r = deg_table_[k];
          do {
            std::cout<<r->deg<<' '<<std::flush;
            r = r->prev;
          } while (r != deg_table_[k]);
          std::cout<<std::endl;
        } else {
          std::cout<<"empty"<<std::endl;
        }
      }
  }

 private:
  bool _CompareNodePriority(const_node_ptr l, const_node_ptr r) const {
    return cond_(l->priority(), r->priority());
  }

  void _PushLink(node_ptr node, node_ptr* link_head) {
    if (!*link_head) {
      *link_head = node;
      node->next = node;
      node->prev = node;
    } else {
      auto b = (*link_head)->prev;
      node->next = *link_head;
      node->prev = b;
      b->next = node;
      (*link_head)->prev = node;
    }
  }

  void _PopLink(node_ptr node, node_ptr* link_head) {
    assert(*link_head);
    if (node->next == node) {
      assert(node->prev == node);
      assert(*link_head == node);
      *link_head = nullptr;
    } else {
      auto n = node->next;
      auto p = node->prev;
      p->next = n;
      n->prev = p;
      if (*link_head == node)
        *link_head = n;
      node->next = node;
      node->prev = node;
    }
  }

  node_ptr _Meld(node_ptr l, node_ptr r) {
    assert(l->deg == r->deg);
    if (_CompareNodePriority(l, r)) {
      std::swap(l, r);
    }
    _PushLink(r, &l->child);
    r->parent = l;
    l->deg++;
    return l;
  }

  void _ExpandChildren(node_ptr node) {
    while (node->child) {
      auto c = node->child;
      _PopLink(c, &node->child);
      --node->deg;
      c->parent = nullptr;
      c->marked = false;
      _PushLink(c, &deg_table_[c->deg]);
    }
    assert(node->deg == 0);
  }

  void _ExtractTop() {
    int k = 0;
    while (k < (int)deg_table_.size()) {
      while (k < (int)deg_table_.size() and !deg_table_[k]) ++k;
      if (k == (int)deg_table_.size())
        break;
      if (deg_table_[k]->next != deg_table_[k]) { // Multiple trees at current degree
        auto node = deg_table_[k];
        _PopLink(node, &deg_table_[k]);
        assert(node->deg == k);
        while (deg_table_[node->deg]) {
          auto d = node->deg;
          auto u = deg_table_[d];
          _PopLink(u, &deg_table_[d]);
          node = _Meld(node, u);
          assert(node->deg == d+1);
        }
        _PushLink(node, &deg_table_[node->deg]);
      } else { // Single tree at current degree
        if (!root_ or _CompareNodePriority(root_, deg_table_[k]))
          root_ = deg_table_[k];
        ++k;
      }
    }
  }

  void _Consolidate(node_ptr node) {
    assert(node->parent);
    auto p = node->parent;
    if (p->marked) {
      assert(p->parent); // Parent is not one of the roots.
      _Consolidate(p);
    }
    assert(!p->marked);
    if (p->parent) {
      p->marked = true;
    } else {
      _PopLink(p, &deg_table_[p->deg]);
      _PushLink(p, &deg_table_[p->deg-1]);
    }
    _PopLink(node, &p->child);
    p->deg--;
    node->parent = nullptr;
    node->marked = false;
    _PushLink(node, &deg_table_[node->deg]);
  }

};
#line 3 "test/aoj/dijkstra_fibonacci.test.cpp"
#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 11e8;

int main() {
  int v,e,r; cin>>v>>e>>r;
  vector<pair<int,int>> G[v];
  for (int i = 0; i < e; i++) {
    int s,t,d; cin>>s>>t>>d;
    G[s].emplace_back(t, d);
  }

  vector<int> dist(v, INF);
  FibonacciHeap<int, greater<>> qs(v);
  dist[r] = 0;
  qs.push(r, 0);
  while (!qs.empty()) {
    auto [s, c] = qs.top(); qs.pop();
    assert(c == dist[s]);
    for (auto [t, d] : G[s]) {
      if (dist[t] <= c + d) continue;
      dist[t] = c + d;
      qs.push(t, c + d);
    }
  }
  for (int i = 0; i < v; i++) {
    if (dist[i] != INF) {
      cout << dist[i] << endl;
    } else {
      cout << "INF" << endl;
    }
  }

}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	3 MB
g++	00_sample_01.in	AC	5 ms	3 MB
g++	01_small_00.in	AC	6 ms	3 MB
g++	01_small_01.in	AC	5 ms	3 MB
g++	02_medium_00.in	AC	5 ms	3 MB
g++	02_medium_01.in	AC	5 ms	3 MB
g++	03_corner_00.in	AC	5 ms	3 MB
g++	03_corner_01.in	AC	6 ms	3 MB
g++	03_corner_02.in	AC	5 ms	3 MB
g++	03_corner_03.in	AC	6 ms	3 MB
g++	04_rand_00.in	AC	6 ms	3 MB
g++	04_rand_01.in	AC	5 ms	3 MB
g++	04_rand_02.in	AC	5 ms	3 MB
g++	04_rand_03.in	AC	5 ms	3 MB
g++	05_linear_00.in	AC	5 ms	3 MB
g++	05_linear_01.in	AC	5 ms	3 MB
g++	05_linear_02.in	AC	5 ms	3 MB
g++	05_linear_03.in	AC	5 ms	3 MB
g++	06_ring_00.in	AC	5 ms	3 MB
g++	06_ring_01.in	AC	5 ms	3 MB
g++	06_ring_02.in	AC	5 ms	3 MB
g++	06_ring_03.in	AC	5 ms	3 MB
g++	07_large_00.in	AC	6 ms	3 MB
g++	07_large_01.in	AC	6 ms	4 MB
g++	07_large_02.in	AC	9 ms	4 MB
g++	07_large_03.in	AC	10 ms	4 MB
g++	08_large_00.in	AC	18 ms	4 MB
g++	08_large_01.in	AC	21 ms	5 MB
g++	08_large_02.in	AC	26 ms	5 MB
g++	08_large_03.in	AC	35 ms	6 MB
g++	09_maximum_00.in	AC	169 ms	10 MB
g++	09_maximum_01.in	AC	408 ms	18 MB
g++	09_maximum_02.in	AC	143 ms	15 MB
g++	09_maximum_03.in	AC	233 ms	15 MB
clang++	00_sample_00.in	AC	6 ms	3 MB
clang++	00_sample_01.in	AC	5 ms	3 MB
clang++	01_small_00.in	AC	5 ms	3 MB
clang++	01_small_01.in	AC	5 ms	3 MB
clang++	02_medium_00.in	AC	5 ms	3 MB
clang++	02_medium_01.in	AC	5 ms	3 MB
clang++	03_corner_00.in	AC	5 ms	3 MB
clang++	03_corner_01.in	AC	5 ms	3 MB
clang++	03_corner_02.in	AC	5 ms	3 MB
clang++	03_corner_03.in	AC	5 ms	3 MB
clang++	04_rand_00.in	AC	5 ms	3 MB
clang++	04_rand_01.in	AC	5 ms	3 MB
clang++	04_rand_02.in	AC	5 ms	3 MB
clang++	04_rand_03.in	AC	5 ms	3 MB
clang++	05_linear_00.in	AC	5 ms	3 MB
clang++	05_linear_01.in	AC	5 ms	3 MB
clang++	05_linear_02.in	AC	5 ms	3 MB
clang++	05_linear_03.in	AC	5 ms	3 MB
clang++	06_ring_00.in	AC	5 ms	3 MB
clang++	06_ring_01.in	AC	5 ms	3 MB
clang++	06_ring_02.in	AC	5 ms	3 MB
clang++	06_ring_03.in	AC	5 ms	3 MB
clang++	07_large_00.in	AC	6 ms	3 MB
clang++	07_large_01.in	AC	7 ms	3 MB
clang++	07_large_02.in	AC	9 ms	4 MB
clang++	07_large_03.in	AC	10 ms	4 MB
clang++	08_large_00.in	AC	18 ms	4 MB
clang++	08_large_01.in	AC	21 ms	5 MB
clang++	08_large_02.in	AC	26 ms	5 MB
clang++	08_large_03.in	AC	35 ms	6 MB
clang++	09_maximum_00.in	AC	170 ms	10 MB
clang++	09_maximum_01.in	AC	407 ms	18 MB
clang++	09_maximum_02.in	AC	142 ms	15 MB
clang++	09_maximum_03.in	AC	252 ms	15 MB

Back to top page