data_structure/test/radix_heap.dijkstra.test.cpp

View this file on GitHub
Last update: 2022-01-08 20:23:44+09:00
Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include "../radix_heap.hpp"
#include "../../utilities/reader.hpp"
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N = rdi(), M = rdi(), s = rdi(), t = rdi();

    vector<vector<pair<int, unsigned>>> to(N);
    while (M--) {
        int a = rdi(), b = rdi(), c = rdi();
        to[b].emplace_back(a, c);
    }
    vector<unsigned long long> dist(N, numeric_limits<unsigned long long>::max());
    vector<int> prv(N, -1);
    dist[t] = 0;
    radix_heap<unsigned long long, int> pq;
    pq.push(0, t);
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int now = p.second;
        if (now == s) break;
        if (dist[now] < p.first) continue;
        for (const auto &nx : to[now]) {
            int nxt = nx.first;
            if (dist[nxt] > dist[now] + nx.second) {
                dist[nxt] = dist[now] + nx.second;
                prv[nxt] = now;
                pq.push(dist[nxt], nxt);
            }
        }
    }
    if (dist[s] == numeric_limits<unsigned long long>::max()) {
        cout << "-1\n";
        return 0;
    }

    std::vector<int> path;
    for (int now = s; now != -1; now = prv[now]) path.push_back(now);
    cout << dist[s] << ' ' << path.size() - 1 << '\n';
    for (int i = 1; i < int(path.size()); i++) cout << path[i - 1] << ' ' << path[i] << '\n';
}

#line 1 "data_structure/test/radix_heap.dijkstra.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#line 2 "data_structure/radix_heap.hpp"
#include <array>
#include <cstddef>
#include <limits>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

// Radix heap for unsigned integer
// https://github.com/iwiwi/radix-heap
template <class Uint, class Label, typename std::enable_if<std::is_unsigned<Uint>::value>::type * = nullptr>
class radix_heap {
    int sz;
    Uint last;
    std::array<std::vector<std::pair<Uint, Label>>, std::numeric_limits<Uint>::digits + 1> v;

    template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>
    static inline int bucket(U x) noexcept {
        return x ? 32 - __builtin_clz(x) : 0;
    }
    template <class U, typename std::enable_if<sizeof(U) == 8>::type * = nullptr>
    static inline int bucket(U x) noexcept {
        return x ? 64 - __builtin_clzll(x) : 0;
    }

    void pull() {
        if (!v[0].empty()) return;
        int i = 1;
        while (v[i].empty()) ++i;
        last = v[i].back().first;
        for (int j = 0; j < int(v[i].size()); j++) last = std::min(last, v[i][j].first);
        for (int j = 0; j < int(v[i].size()); j++) {
            v[bucket(v[i][j].first ^ last)].emplace_back(std::move(v[i][j]));
        }
        v[i].clear();
    }

public:
    radix_heap() : sz(0), last(0) {
        static_assert(std::numeric_limits<Uint>::digits > 0, "Invalid type.");
    }
    std::size_t size() const noexcept { return sz; }
    bool empty() const noexcept { return sz == 0; }
    void push(Uint x, const Label &val) { ++sz, v[bucket(x ^ last)].emplace_back(x, val); }
    void push(Uint x, Label &&val) { ++sz, v[bucket(x ^ last)].emplace_back(x, std::move(val)); }
    template <class... Args> void emplace(Uint x, Args &&...args) {
        ++sz, v[bucket(x ^ last)].emplace_back(std::piecewise_construct, std::forward_as_tuple(x),
                                               std::forward_as_tuple(args...));
    }
    void pop() { pull(), --sz, v[0].pop_back(); }
    std::pair<Uint, Label> top() { return pull(), v[0].back(); }
    Uint top_key() { return pull(), last; }
    Label &top_label() { return pull(), v[0].back().second; }
    void clear() noexcept {
        sz = 0, last = 0;
        for (auto &vec : v) vec.clear();
    }
    void swap(radix_heap<Uint, Label> &a) {
        std::swap(sz, a.sz), std::swap(last, a.last), v.swap(a.v);
    }
};
#line 2 "utilities/reader.hpp"
#include <cstdio>
#include <string>

// CUT begin
template <typename T> T rd_integer() {
    T ret = 0;
    bool minus = false;

    char c = getchar_unlocked();
    while (!isdigit(c)) minus |= (c == '-'), c = getchar_unlocked();
    while (isdigit(c)) ret = (ret << 1) + (ret << 3) + (c ^ 48), c = getchar_unlocked();

    return minus ? -ret : ret;
}
int rdi() { return rd_integer<int>(); }
long long rdll() { return rd_integer<long long>(); }
std::string rdstr() {
    std::string ret;
    char c = getchar_unlocked();
    while (!isgraph(c)) c = getchar_unlocked();
    while (isgraph(c)) ret += c, c = getchar_unlocked();
    return ret;
}
#line 4 "data_structure/test/radix_heap.dijkstra.test.cpp"
#include <iostream>
#line 8 "data_structure/test/radix_heap.dijkstra.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N = rdi(), M = rdi(), s = rdi(), t = rdi();

    vector<vector<pair<int, unsigned>>> to(N);
    while (M--) {
        int a = rdi(), b = rdi(), c = rdi();
        to[b].emplace_back(a, c);
    }
    vector<unsigned long long> dist(N, numeric_limits<unsigned long long>::max());
    vector<int> prv(N, -1);
    dist[t] = 0;
    radix_heap<unsigned long long, int> pq;
    pq.push(0, t);
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int now = p.second;
        if (now == s) break;
        if (dist[now] < p.first) continue;
        for (const auto &nx : to[now]) {
            int nxt = nx.first;
            if (dist[nxt] > dist[now] + nx.second) {
                dist[nxt] = dist[now] + nx.second;
                prv[nxt] = now;
                pq.push(dist[nxt], nxt);
            }
        }
    }
    if (dist[s] == numeric_limits<unsigned long long>::max()) {
        cout << "-1\n";
        return 0;
    }

    std::vector<int> path;
    for (int now = s; now != -1; now = prv[now]) path.push_back(now);
    cout << dist[s] << ' ' << path.size() - 1 << '\n';
    for (int i = 1; i < int(path.size()); i++) cout << path[i - 1] << ' ' << path[i] << '\n';
}