k_shortest_walk.hpp¶
按长度顺序求源点到终点的前 \(k\) 条游走，允许重复经过顶点和边。
Complexity: Time: \(O((V + E) \log (E + 2) + k \log (k + 2))\). Space: \(O(V + E + V \log (E + 2) + k)\).
AC 记录：k_shortest_walk。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((V + E) log(E + 2) + k log(k + 2)).
/// Space: O(V + E + V log(E + 2) + k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace k_shortest_walk_internal {
template <class Weight> struct persistent_leftist_heap {
struct node {
Weight val{};
int to1 = -1, l = -1, r = -1, rk = 1;
};
std::vector<node> nd;
int node_rank(int id) const { return id == -1 ? 0 : nd[id].rk; }
int append(node x) {
assert(nd.size() < std::size_t(std::numeric_limits<int>::max()));
nd.push_back(x);
return int(nd.size()) - 1;
}
int meld(int a, int b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
if (nd[b].val < nd[a].val) std::swap(a, b);
node x = nd[a];
x.r = meld(x.r, b);
if (node_rank(x.l) < node_rank(x.r)) std::swap(x.l, x.r);
x.rk = node_rank(x.r) + 1;
return append(x);
}
// Newly appended nodes have no external references. Heapify them in O(d);
// a complete binary heap is leftist, so it can join the persistent heap.
int build(int first) {
std::size_t count = nd.size() - first;
if (count == 0) return -1;
std::make_heap(nd.begin() + first, nd.end(),
[](const node &a, const node &b) { return b.val < a.val; });
for (std::size_t i = count; i-- > 0;) {
auto &x = nd[first + i];
std::size_t l = 2 * i + 1, r = l + 1;
x.l = l < count ? int(first + l) : -1;
x.r = r < count ? int(first + r) : -1;
x.rk = node_rank(x.r) + 1;
}
return first;
}
};
} // namespace k_shortest_walk_internal
/// @brief First cnt representable lengths of directed walks from s to t,
/// in nondecreasing order. Edges and vertices may repeat; parallel edges
/// define distinct walks. The empty walk is included when s == t.
/// Weights are nonnegative and arithmetic must be exact, as for integers.
/// Lengths beyond numeric_limits<Weight>::max() are omitted. If fewer than
/// cnt representable walks exist, return all of them. Input is unchanged.
/// Edge count and the persistent heap's total node count must fit int.
template <class Weight>
std::vector<Weight>
k_shortest_walk_lengths(int n,
const std::vector<std::tuple<int, int, Weight>> &es,
int s, int t, int cnt) {
assert(n >= 0 && 0 <= s && s < n && 0 <= t && t < n && cnt >= 0);
if (cnt == 0) return {};
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<int> head(std::size_t(n) + 1), ids(m);
for (auto [u, v, w] : es) {
assert(0 <= u && u < n && 0 <= v && v < n && w >= Weight{});
++head[v + 1];
}
for (int u = 0; u < n; ++u) head[u + 1] += head[u];
auto cursor = head;
for (int id = 0; id < m; ++id) ids[cursor[std::get<1>(es[id])]++] = id;
const Weight maximum = std::numeric_limits<Weight>::max();
std::vector<Weight> dis(n, maximum);
std::vector<char> reached(n);
std::vector<int> pe(n, -1), parent(n, -1), order;
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> queue;
reached[t] = 1;
dis[t] = Weight{};
queue.emplace(Weight{}, t);
while (!queue.empty()) {
auto [du, u] = queue.top();
queue.pop();
if (du != dis[u]) continue;
if (cnt == 1 && u == s) return {du};
// A chosen tree parent was settled before its child, even on zero edges.
order.push_back(u);
for (int j = head[u]; j < head[u + 1]; ++j) {
int id = ids[j];
auto [v, to, w] = es[id];
if (w > maximum - du) continue;
Weight candidate = du + w;
if (!reached[v] || candidate < dis[v]) {
reached[v] = 1;
dis[v] = candidate;
parent[v] = u;
pe[v] = id;
queue.emplace(candidate, v);
}
}
}
if (!reached[s]) return {};
// Reverse adjacency is no longer needed; reuse its buffers for outgoing IDs.
std::fill(head.begin(), head.end(), 0);
for (auto [u, v, w] : es) ++head[u + 1];
for (int u = 0; u < n; ++u) head[u + 1] += head[u];
cursor = head;
for (int id = 0; id < m; ++id) ids[cursor[std::get<0>(es[id])]++] = id;
k_shortest_walk_internal::persistent_leftist_heap<Weight> heap;
std::vector<int> roots(n, -1);
for (int u : order) {
int first = int(heap.nd.size());
for (int j = head[u]; j < head[u + 1]; ++j) {
int id = ids[j];
auto [from, v, w] = es[id];
if (id == pe[u] || !reached[v]) continue;
Weight sidetrack;
// Evaluate w + dis[v] - dis[u] without overflowing a cancelling sum.
if (dis[v] >= dis[u]) {
Weight gap = dis[v] - dis[u];
if (w > maximum - gap) continue;
sidetrack = w + gap;
} else {
sidetrack = w - (dis[u] - dis[v]);
}
heap.append({sidetrack, v});
}
int local = heap.build(first);
int inherited = parent[u] == -1 ? -1 : roots[parent[u]];
roots[u] = heap.meld(inherited, local);
}
// A walk is its shortest base path plus an ordered sequence of sidetracks.
std::priority_queue<state, std::vector<state>, std::greater<state>> candidates;
candidates.emplace(dis[s], -1);
std::vector<Weight> result;
auto push = [&](Weight total, Weight delta, int node) {
if (delta <= maximum - total) candidates.emplace(total + delta, node);
};
while (!candidates.empty()) {
auto [total, id] = candidates.top();
candidates.pop();
result.push_back(total);
if (int(result.size()) == cnt) break;
int next;
if (id == -1) {
next = roots[s];
} else {
const auto &node = heap.nd[id];
for (int child : {node.l, node.r}) if (child != -1)
push(total, heap.nd[child].val - node.val, child);
next = roots[node.to1];
}
if (next != -1) push(total, heap.nd[next].val, next);
}
return result;
}
} // namespace noya
// NOYA_K_SHORTEST_WALK_HPP
#ifndef NOYA_K_SHORTEST_WALK_HPP
#define NOYA_K_SHORTEST_WALK_HPP 1
/// @complexity Time: O((V + E) log(E + 2) + k log(k + 2)).
/// Space: O(V + E + V log(E + 2) + k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace k_shortest_walk_internal {
template <class Weight> struct persistent_leftist_heap {
struct node {
Weight val{};
int to1 = -1, l = -1, r = -1, rk = 1;
};
std::vector<node> nd;
int node_rank(int id) const { return id == -1 ? 0 : nd[id].rk; }
int append(node x) {
assert(nd.size() < std::size_t(std::numeric_limits<int>::max()));
nd.push_back(x);
return int(nd.size()) - 1;
}
int meld(int a, int b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
if (nd[b].val < nd[a].val) std::swap(a, b);
node x = nd[a];
x.r = meld(x.r, b);
if (node_rank(x.l) < node_rank(x.r)) std::swap(x.l, x.r);
x.rk = node_rank(x.r) + 1;
return append(x);
}
// Newly appended nodes have no external references. Heapify them in O(d);
// a complete binary heap is leftist, so it can join the persistent heap.
int build(int first) {
std::size_t count = nd.size() - first;
if (count == 0) return -1;
std::make_heap(nd.begin() + first, nd.end(),
[](const node &a, const node &b) { return b.val < a.val; });
for (std::size_t i = count; i-- > 0;) {
auto &x = nd[first + i];
std::size_t l = 2 * i + 1, r = l + 1;
x.l = l < count ? int(first + l) : -1;
x.r = r < count ? int(first + r) : -1;
x.rk = node_rank(x.r) + 1;
}
return first;
}
};
} // namespace k_shortest_walk_internal
/// @brief First cnt representable lengths of directed walks from s to t,
/// in nondecreasing order. Edges and vertices may repeat; parallel edges
/// define distinct walks. The empty walk is included when s == t.
/// Weights are nonnegative and arithmetic must be exact, as for integers.
/// Lengths beyond numeric_limits<Weight>::max() are omitted. If fewer than
/// cnt representable walks exist, return all of them. Input is unchanged.
/// Edge count and the persistent heap's total node count must fit int.
template <class Weight>
std::vector<Weight>
k_shortest_walk_lengths(int n,
const std::vector<std::tuple<int, int, Weight>> &es,
int s, int t, int cnt) {
assert(n >= 0 && 0 <= s && s < n && 0 <= t && t < n && cnt >= 0);
if (cnt == 0) return {};
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<int> head(std::size_t(n) + 1), ids(m);
for (auto [u, v, w] : es) {
assert(0 <= u && u < n && 0 <= v && v < n && w >= Weight{});
++head[v + 1];
}
for (int u = 0; u < n; ++u) head[u + 1] += head[u];
auto cursor = head;
for (int id = 0; id < m; ++id) ids[cursor[std::get<1>(es[id])]++] = id;
const Weight maximum = std::numeric_limits<Weight>::max();
std::vector<Weight> dis(n, maximum);
std::vector<char> reached(n);
std::vector<int> pe(n, -1), parent(n, -1), order;
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> queue;
reached[t] = 1;
dis[t] = Weight{};
queue.emplace(Weight{}, t);
while (!queue.empty()) {
auto [du, u] = queue.top();
queue.pop();
if (du != dis[u]) continue;
if (cnt == 1 && u == s) return {du};
// A chosen tree parent was settled before its child, even on zero edges.
order.push_back(u);
for (int j = head[u]; j < head[u + 1]; ++j) {
int id = ids[j];
auto [v, to, w] = es[id];
if (w > maximum - du) continue;
Weight candidate = du + w;
if (!reached[v] || candidate < dis[v]) {
reached[v] = 1;
dis[v] = candidate;
parent[v] = u;
pe[v] = id;
queue.emplace(candidate, v);
}
}
}
if (!reached[s]) return {};
// Reverse adjacency is no longer needed; reuse its buffers for outgoing IDs.
std::fill(head.begin(), head.end(), 0);
for (auto [u, v, w] : es) ++head[u + 1];
for (int u = 0; u < n; ++u) head[u + 1] += head[u];
cursor = head;
for (int id = 0; id < m; ++id) ids[cursor[std::get<0>(es[id])]++] = id;
k_shortest_walk_internal::persistent_leftist_heap<Weight> heap;
std::vector<int> roots(n, -1);
for (int u : order) {
int first = int(heap.nd.size());
for (int j = head[u]; j < head[u + 1]; ++j) {
int id = ids[j];
auto [from, v, w] = es[id];
if (id == pe[u] || !reached[v]) continue;
Weight sidetrack;
// Evaluate w + dis[v] - dis[u] without overflowing a cancelling sum.
if (dis[v] >= dis[u]) {
Weight gap = dis[v] - dis[u];
if (w > maximum - gap) continue;
sidetrack = w + gap;
} else {
sidetrack = w - (dis[u] - dis[v]);
}
heap.append({sidetrack, v});
}
int local = heap.build(first);
int inherited = parent[u] == -1 ? -1 : roots[parent[u]];
roots[u] = heap.meld(inherited, local);
}
// A walk is its shortest base path plus an ordered sequence of sidetracks.
std::priority_queue<state, std::vector<state>, std::greater<state>> candidates;
candidates.emplace(dis[s], -1);
std::vector<Weight> result;
auto push = [&](Weight total, Weight delta, int node) {
if (delta <= maximum - total) candidates.emplace(total + delta, node);
};
while (!candidates.empty()) {
auto [total, id] = candidates.top();
candidates.pop();
result.push_back(total);
if (int(result.size()) == cnt) break;
int next;
if (id == -1) {
next = roots[s];
} else {
const auto &node = heap.nd[id];
for (int child : {node.l, node.r}) if (child != -1)
push(total, heap.nd[child].val - node.val, child);
next = roots[node.to1];
}
if (next != -1) push(total, heap.nd[next].val, next);
}
return result;
}
} // namespace noya
#endif // NOYA_K_SHORTEST_WALK_HPP
/// @complexity Time: O((V + E) log(E + 2) + k log(k + 2)).
/// Space: O(V + E + V log(E + 2) + k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace k_shortest_walk_internal {
template <class Weight> struct persistent_leftist_heap {
struct node {
Weight val{};
int to1 = -1, l = -1, r = -1, rk = 1;
};
std::vector<node> nd;
int node_rank(int id) const { return id == -1 ? 0 : nd[id].rk; }
int append(node x) {
assert(nd.size() < std::size_t(std::numeric_limits<int>::max()));
nd.push_back(x);
return int(nd.size()) - 1;
}
int meld(int a, int b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
if (nd[b].val < nd[a].val) std::swap(a, b);
node x = nd[a];
x.r = meld(x.r, b);
if (node_rank(x.l) < node_rank(x.r)) std::swap(x.l, x.r);
x.rk = node_rank(x.r) + 1;
return append(x);
}
// Newly appended nodes have no external references. Heapify them in O(d);
// a complete binary heap is leftist, so it can join the persistent heap.
int build(int first) {
std::size_t count = nd.size() - first;
if (count == 0) return -1;
std::make_heap(nd.begin() + first, nd.end(),
[](const node &a, const node &b) { return b.val < a.val; });
for (std::size_t i = count; i-- > 0;) {
auto &x = nd[first + i];
std::size_t l = 2 * i + 1, r = l + 1;
x.l = l < count ? int(first + l) : -1;
x.r = r < count ? int(first + r) : -1;
x.rk = node_rank(x.r) + 1;
}
return first;
}
};
} // namespace k_shortest_walk_internal
/// @brief First cnt representable lengths of directed walks from s to t,
/// in nondecreasing order. Edges and vertices may repeat; parallel edges
/// define distinct walks. The empty walk is included when s == t.
/// Weights are nonnegative and arithmetic must be exact, as for integers.
/// Lengths beyond numeric_limits<Weight>::max() are omitted. If fewer than
/// cnt representable walks exist, return all of them. Input is unchanged.
/// Edge count and the persistent heap's total node count must fit int.
template <class Weight>
std::vector<Weight>
k_shortest_walk_lengths(int n,
const std::vector<std::tuple<int, int, Weight>> &es,
int s, int t, int cnt) {
assert(n >= 0 && 0 <= s && s < n && 0 <= t && t < n && cnt >= 0);
if (cnt == 0) return {};
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
int m = int(es.size());
std::vector<int> head(std::size_t(n) + 1), ids(m);
for (auto [u, v, w] : es) {
assert(0 <= u && u < n && 0 <= v && v < n && w >= Weight{});
++head[v + 1];
}
for (int u = 0; u < n; ++u) head[u + 1] += head[u];
auto cursor = head;
for (int id = 0; id < m; ++id) ids[cursor[std::get<1>(es[id])]++] = id;
const Weight maximum = std::numeric_limits<Weight>::max();
std::vector<Weight> dis(n, maximum);
std::vector<char> reached(n);
std::vector<int> pe(n, -1), parent(n, -1), order;
using state = std::pair<Weight, int>;
std::priority_queue<state, std::vector<state>, std::greater<state>> queue;
reached[t] = 1;
dis[t] = Weight{};
queue.emplace(Weight{}, t);
while (!queue.empty()) {
auto [du, u] = queue.top();
queue.pop();
if (du != dis[u]) continue;
if (cnt == 1 && u == s) return {du};
// A chosen tree parent was settled before its child, even on zero edges.
order.push_back(u);
for (int j = head[u]; j < head[u + 1]; ++j) {
int id = ids[j];
auto [v, to, w] = es[id];
if (w > maximum - du) continue;
Weight candidate = du + w;
if (!reached[v] || candidate < dis[v]) {
reached[v] = 1;
dis[v] = candidate;
parent[v] = u;
pe[v] = id;
queue.emplace(candidate, v);
}
}
}
if (!reached[s]) return {};
// Reverse adjacency is no longer needed; reuse its buffers for outgoing IDs.
std::fill(head.begin(), head.end(), 0);
for (auto [u, v, w] : es) ++head[u + 1];
for (int u = 0; u < n; ++u) head[u + 1] += head[u];
cursor = head;
for (int id = 0; id < m; ++id) ids[cursor[std::get<0>(es[id])]++] = id;
k_shortest_walk_internal::persistent_leftist_heap<Weight> heap;
std::vector<int> roots(n, -1);
for (int u : order) {
int first = int(heap.nd.size());
for (int j = head[u]; j < head[u + 1]; ++j) {
int id = ids[j];
auto [from, v, w] = es[id];
if (id == pe[u] || !reached[v]) continue;
Weight sidetrack;
// Evaluate w + dis[v] - dis[u] without overflowing a cancelling sum.
if (dis[v] >= dis[u]) {
Weight gap = dis[v] - dis[u];
if (w > maximum - gap) continue;
sidetrack = w + gap;
} else {
sidetrack = w - (dis[u] - dis[v]);
}
heap.append({sidetrack, v});
}
int local = heap.build(first);
int inherited = parent[u] == -1 ? -1 : roots[parent[u]];
roots[u] = heap.meld(inherited, local);
}
// A walk is its shortest base path plus an ordered sequence of sidetracks.
std::priority_queue<state, std::vector<state>, std::greater<state>> candidates;
candidates.emplace(dis[s], -1);
std::vector<Weight> result;
auto push = [&](Weight total, Weight delta, int node) {
if (delta <= maximum - total) candidates.emplace(total + delta, node);
};
while (!candidates.empty()) {
auto [total, id] = candidates.top();
candidates.pop();
result.push_back(total);
if (int(result.size()) == cnt) break;
int next;
if (id == -1) {
next = roots[s];
} else {
const auto &node = heap.nd[id];
for (int child : {node.l, node.r}) if (child != -1)
push(total, heap.nd[child].val - node.val, child);
next = roots[node.to1];
}
if (next != -1) push(total, heap.nd[next].val, next);
}
return result;
}
} // namespace noya
// NOYA_K_SHORTEST_WALK_HPP