#pragma once
#include "../data-structure/radix-heap.hpp"
#include "../graph/graph-template.hpp"
// unreachable -> {-1, -1}
template <typename T>
vector<pair<T, int>> dijkstra_restore(WeightedGraph<T> &g, int start = 0) {
int N = (int)g.size();
using P = pair<T, int>;
vector<P> d(N, P{-1, -1});
RadixHeap<T, int> Q;
d[start].first = 0;
Q.push(0, start);
while (!Q.empty()) {
auto p = Q.pop();
int cur = p.second;
T dc = d[cur].first;
if (dc < T(p.first)) continue;
for (auto dst : g[cur]) {
if (d[dst].first == T(-1) || dc + dst.cost < d[dst].first) {
d[dst] = P{dc + dst.cost, cur};
Q.push(dc + dst.cost, dst);
}
}
}
return d;
}
/*
* @brief ダイクストラ法(復元付き)
**/
#line 2 "shortest-path/dijkstra-with-restore.hpp"
#line 2 "data-structure/radix-heap.hpp"
template <typename Key, typename Val>
struct RadixHeap {
using uint = typename make_unsigned<Key>::type;
static constexpr int bit = sizeof(Key) * 8;
array<vector<pair<uint, Val> >, bit + 1> vs;
array<uint, bit + 1> ms;
int s;
uint last;
RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); }
bool empty() const { return s == 0; }
int size() const { return s; }
__attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const {
return 64 - _lzcnt_u64(a);
}
void push(const uint &key, const Val &val) {
s++;
uint64_t b = getbit(key ^ last);
vs[b].emplace_back(key, val);
ms[b] = min(key, ms[b]);
}
pair<uint, Val> pop() {
if (ms[0] == uint(-1)) {
int idx = 1;
while (ms[idx] == uint(-1)) idx++;
last = ms[idx];
for (auto &p : vs[idx]) {
uint64_t b = getbit(p.first ^ last);
vs[b].emplace_back(p);
ms[b] = min(p.first, ms[b]);
}
vs[idx].clear();
ms[idx] = uint(-1);
}
--s;
auto res = vs[0].back();
vs[0].pop_back();
if (vs[0].empty()) ms[0] = uint(-1);
return res;
}
};
/**
* @brief Radix Heap
*/
#line 2 "graph/graph-template.hpp"
template <typename T>
struct edge {
int src, to;
T cost;
edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}
edge &operator=(const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;
// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
UnweightedGraph g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
if (is_1origin) x--, y--;
g[x].push_back(y);
if (!is_directed) g[y].push_back(x);
}
return g;
}
// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
WeightedGraph<T> g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
cin >> c;
if (is_1origin) x--, y--;
g[x].emplace_back(x, y, c);
if (!is_directed) g[y].emplace_back(y, x, c);
}
return g;
}
// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true,
bool is_1origin = true) {
Edges<T> es;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
es.emplace_back(x, y, c);
}
return es;
}
// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
bool is_directed = false, bool is_1origin = true) {
vector<vector<T>> d(N, vector<T>(N, INF));
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
d[x][y] = c;
if (!is_directed) d[y][x] = c;
}
return d;
}
/**
* @brief グラフテンプレート
*/
#line 7 "shortest-path/dijkstra-with-restore.hpp"
// unreachable -> {-1, -1}
template <typename T>
vector<pair<T, int>> dijkstra_restore(WeightedGraph<T> &g, int start = 0) {
int N = (int)g.size();
using P = pair<T, int>;
vector<P> d(N, P{-1, -1});
RadixHeap<T, int> Q;
d[start].first = 0;
Q.push(0, start);
while (!Q.empty()) {
auto p = Q.pop();
int cur = p.second;
T dc = d[cur].first;
if (dc < T(p.first)) continue;
for (auto dst : g[cur]) {
if (d[dst].first == T(-1) || dc + dst.cost < d[dst].first) {
d[dst] = P{dc + dst.cost, cur};
Q.push(dc + dst.cost, dst);
}
}
}
return d;
}
/*
* @brief ダイクストラ法(復元付き)
**/
ダイクストラ法(復元付き)