fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define rep(i, n) for (int i = 0; i < (n); i++)
  4. #define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
  5. #define rep2(i, l, r) for (int i = (l); i < (r); i++)
  6. #define rep2r(i, l, r) for (int i = (r) - 1; i >= (l); i--)
  7. #define range(a) a.begin(), a.end()
  8.  
  9. using namespace std;
  10. using ll = long long;
  11.  
  12. template<class A, class B>
  13. ostream &operator<<(ostream &o, pair<A, B> a) {
  14.   return o << "(" << a.first << "," << a.second << ")";
  15. }
  16.  
  17. template<class T>
  18. ostream &operator<<(ostream &o, vector<T> a) {
  19.   o << '[';
  20.   for (size_t i = 0; i < a.size(); i++) {
  21.     if (i > 0) o << ',';
  22.     o << a[i];
  23.   }
  24.   o << ']';
  25.   return o;
  26. }
  27.  
  28. template<class T>
  29. struct fibonacci_heap {
  30.   int mn;
  31.  
  32.   struct node {
  33.     int l; // left
  34.     int r; // right
  35.     int p; // parent
  36.     int c; // children
  37.     int d; // degree
  38.     T key; // value
  39.     bool mark;
  40.   };
  41.  
  42.   int root;
  43.   vector<node> dat;
  44.  
  45.   fibonacci_heap(int n, T inf) : dat(n) {
  46.     root = 0;
  47.     mn = 0;
  48.     for (int i = 0; i < n; i++) {
  49.       dat[i].l = (i + n - 1) % n;
  50.       dat[i].r = (i + 1) % n;
  51.       dat[i].p = -1;
  52.       dat[i].c = -1;
  53.       dat[i].d = 0;
  54.       dat[i].key = inf;
  55.       dat[i].mark = false;
  56.     }
  57.   }
  58.  
  59.   void insert_list(int *z, int x, int p) {
  60.     dat[x].p = p;
  61.     if (p != -1) dat[p].d++;
  62.     if (*z == -1) {
  63.       *z = x;
  64.       dat[x].l = x;
  65.       dat[x].r = x;
  66.       return;
  67.     }
  68.     int y = dat[*z].r;
  69.     dat[*z].r = x;
  70.     dat[y].l = x;
  71.     dat[x].l = *z;
  72.     dat[x].r = y;
  73.   }
  74.  
  75.   void remove_list(int *z, int x) {
  76.     int p = dat[x].p;
  77.     if (p != -1) dat[p].d--;
  78.     if (*z == x) {
  79.       *z = dat[x].r;
  80.       if (*z == x) {
  81.         *z = -1;
  82.         return;
  83.       }
  84.     }
  85.     int l = dat[x].l;
  86.     int r = dat[x].r;
  87.     dat[l].r = r;
  88.     dat[r].l = l;
  89.   }
  90.  
  91.   vector<int> make_list(int x) {
  92.     if (x == -1) return {};
  93.     vector<int> res;
  94.     int y = x;
  95.     do {
  96.       res.push_back(y);
  97.       y = dat[y].r;
  98.     } while (y != x);
  99.     return res;
  100.   }
  101.  
  102.   pair<T, int> extract_min() {
  103.     int z = mn;
  104.     pair<T, int> res(dat[mn].key, mn);
  105.     int c = dat[z].c;
  106.     vector<int> children = make_list(c);
  107.     for (int c : children) {
  108.       insert_list(&root, c, -1);
  109.     }
  110.     mn = dat[z].r;
  111.     remove_list(&root, z);
  112.     if (root == -1) mn = -1;
  113.     if (z == root) root = dat[z].r;
  114.     else consolidate();
  115.     return res;
  116.   }
  117.  
  118.   void consolidate() {
  119.     vector<int> A(40, -1);
  120.     int w = root;
  121.     vector<int> children = make_list(root);
  122.     for (int w : children) {
  123.       if (dat[w].p != -1) continue;
  124.       int x = w;
  125.       int d = dat[x].d;
  126.       while (A[d] != -1) {
  127.         int y = A[d];
  128.         if (dat[x].key > dat[y].key) {
  129.           swap(x, y);
  130.         }
  131.         fib_heap_link(y, x);
  132.         A[d] = -1;
  133.         d++;
  134.       }
  135.       A[d] = x;
  136.     }
  137.     mn = -1;
  138.     root = -1;
  139.     for (int i = 0; i < A.size(); i++) {
  140.       if (A[i] != -1) {
  141.         insert_list(&root, A[i], -1);
  142.         if (mn == -1 || dat[A[i]].key < dat[mn].key) {
  143.           mn = A[i];
  144.         }
  145.       }
  146.     }
  147.   }
  148.  
  149.   void fib_heap_link(int y, int x) {
  150.     remove_list(&root, y);
  151.     insert_list(&dat[x].c, y, x);
  152.     dat[y].mark = false;
  153.   }
  154.  
  155.   void decrease_key(int x, T v) {
  156.     assert(dat[x].key >= v);
  157.     dat[x].key = v;
  158.     int y = dat[x].p;
  159.     if (y != -1 && dat[x].key < dat[y].key) {
  160.       cut(x, y);
  161.       cascading_cut(y);
  162.     }
  163.     if (dat[x].key < dat[mn].key) {
  164.       mn = x;
  165.     }
  166.   }
  167.  
  168.   void cut(int x, int y) {
  169.     remove_list(&dat[y].c, x);
  170.     insert_list(&root, x, -1);
  171.     dat[x].mark = false;
  172.   }
  173.  
  174.   void cascading_cut(int y) {
  175.     int z = dat[y].p;
  176.     if (z != -1) {
  177.       if (!dat[y].mark) {
  178.         dat[y].mark = true;
  179.       } else {
  180.         cut(y, z);
  181.         cascading_cut(z);
  182.       }
  183.     }
  184.   }
  185. };
  186.  
  187. template<class T>
  188. struct binary_heap {
  189.   vector<T> key;
  190.   vector<int> hv;
  191.   vector<int> vh;
  192.  
  193.   binary_heap(int n, T inf) : key(n, inf), hv(n), vh(n) {
  194.     for (int i = 0; i < n; i++) {
  195.       hv[i] = i;
  196.       vh[i] = i;
  197.     }
  198.   }
  199.  
  200.   void exchange(int x, int y) {
  201.     swap(key[x], key[y]);
  202.     int X = hv[x];
  203.     int Y = hv[y];
  204.     swap(vh[X], vh[Y]);
  205.     swap(hv[x], hv[y]);
  206.   }
  207.  
  208.   pair<T, int> extract_min() {
  209.     pair<T, int> res(key[0], hv[0]);
  210.     exchange(0, key.size() - 1);
  211.     key.pop_back();
  212.     const int n = key.size();
  213.     int k = 0;
  214.     for (;;) {
  215.       int l = k;
  216.       if (k * 2 + 1 < n && key[k * 2 + 1] < key[l]) l = k * 2 + 1;
  217.       if (k * 2 + 2 < n && key[k * 2 + 2] < key[l]) l = k * 2 + 2;
  218.       if (l == k) break;
  219.       exchange(k, l);
  220.       k = l;
  221.     }
  222.     return res;
  223.   }
  224.  
  225.   void decrease_key(int x, T v) {
  226.     x = vh[x];
  227.     assert(key[x] >= v);
  228.     key[x] = v;
  229.     while (x > 0) {
  230.       int p = (x - 1) >> 1;
  231.       if (key[p] > key[x]) {
  232.         exchange(p, x);
  233.         x = p;
  234.       } else break;
  235.     }
  236.   }
  237. };
  238.  
  239. int main() {
  240.   cin.tie(nullptr);
  241.   ios::sync_with_stdio(false);
  242.   cout << fixed << setprecision(15);
  243.   const int n = 5000;
  244.   vector<vector<int>> G(n, vector<int>(n, 1e9));
  245.   mt19937 mt(123);
  246.   rep(i, n) rep2(j, i + 1, n) G[i][j] = (n - i) * 5000 + uniform_int_distribution<int>(0, 4999)(mt);
  247.   rep(i, n - 1) G[i][i + 1] = 0;
  248. {
  249.   clock_t beg = clock();
  250.   constexpr int INF = 1e9;
  251.   fibonacci_heap<int> hp(n, INF);
  252.   vector<int> d(n, INF);
  253.   d[0] = 0;
  254.   hp.decrease_key(0, 0);
  255.   int cnt = 0;
  256.   for (int ii = 0; ii < n; ii++) {
  257.     int u = hp.extract_min().second;
  258.     if (d[u] == INF) break;
  259.     rep(v, n) {
  260.       if (d[v] > d[u] + G[u][v]) {
  261.         d[v] = d[u] + G[u][v];
  262.         hp.decrease_key(v, d[v]);
  263.         cnt++;
  264.       }
  265.     }
  266.   }
  267.   clock_t end = clock();
  268.   cout << "fibonacci heap : " << (double)(end - beg) / CLOCKS_PER_SEC * 1000 << endl;
  269.   cout << cnt << endl;
  270. }
  271. {
  272.   clock_t beg = clock();
  273.   constexpr int INF = 1e9;
  274.   binary_heap<int> hp(n, INF);
  275.   vector<int> d(n, INF);
  276.   d[0] = 0;
  277.   hp.decrease_key(0, 0);
  278.   int cnt = 0;
  279.   for (int ii = 0; ii < n; ii++) {
  280.     int u = hp.extract_min().second;
  281.     if (d[u] == INF) break;
  282.     rep(v, n) {
  283.       if (d[v] > d[u] + G[u][v]) {
  284.         d[v] = d[u] + G[u][v];
  285.         hp.decrease_key(v, d[v]);
  286.         cnt++;
  287.       }
  288.     }
  289.   }
  290.   clock_t end = clock();
  291.   cout << "binary heap with decrease key : " << (double)(end - beg) / CLOCKS_PER_SEC * 1000 << endl;
  292.   cout << cnt << endl;
  293. }
  294. {
  295.   clock_t beg = clock();
  296.   constexpr int INF = 1e9;
  297.   priority_queue<pair<int, int>> hp;
  298.   vector<int> dist(n, INF);
  299.   dist[0] = 0;
  300.   hp.emplace(0, 0);
  301.   int cnt = 0;
  302.   while (!hp.empty()) {
  303.     int d = -hp.top().first;
  304.     int u = hp.top().second;
  305.     hp.pop();
  306.     if (dist[u] < d) continue;
  307.     rep(v, n) {
  308.       if (dist[v] > dist[u] + G[u][v]) {
  309.         dist[v] = dist[u] + G[u][v];
  310.         hp.emplace(-dist[v], v);
  311.         cnt++;
  312.       }
  313.     }
  314.   }
  315.   clock_t end = clock();
  316.   cout << "binary heap without decrease key : " << (double)(end - beg) / CLOCKS_PER_SEC * 1000 << endl;
  317.   cout << cnt << endl;
  318. }
  319. {
  320.   clock_t beg = clock();
  321.   constexpr int INF = 1e9;
  322.   vector<int> dist(n, INF);
  323.   dist[0] = 0;
  324.   int cnt = 0;
  325.   vector<bool> used(n);
  326.   rep(ii, n) {
  327.     int u = min_element(range(dist)) - dist.begin();
  328.     if (dist[u] == INF) break;
  329.     used[u] = true;
  330.     rep(v, n) {
  331.       if (!used[v] && dist[v] > dist[u] + G[u][v]) {
  332.         dist[v] = dist[u] + G[u][v];
  333.         cnt++;
  334.       }
  335.     }
  336.     dist[u] = INF;
  337.   }
  338.   clock_t end = clock();
  339.   cout << "straight forward : " << (double)(end - beg) / CLOCKS_PER_SEC * 1000 << endl;
  340.   cout << cnt << endl;
  341. }
  342. }
  343.  
Success #stdin #stdout 2.57s 232588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
fibonacci heap : 384.055999999999983
12497500
binary heap with decrease key : 201.893000000000001
12497500
binary heap without decrease key : 1539.754000000000133
12497500
straight forward : 94.238000000000000
12497500
https://ideone.com/IVsxkl
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!