shortest_path.hpp¶
提供 BFS、01-BFS、Dijkstra、Bellman-Ford、任意负环边序与 Floyd；按边权范围选用，区分不可达、有限距离饱和与负无穷，并沿合法前驱链恢复路径。
Complexity: Time: \(O(V + E)\) BFS/0-1 BFS, \(O(V + E \log (E + 2))\) Dijkstra, \(O(V + VE)\) Bellman-Ford/negative-cycle search, \(O(V^{3})\) Floyd, \(O(\text{path length})\) recovery. Space: \(O(V)\) BFS/0-1 BFS/signed-cycle routines, \(O(V + E)\) Dijkstra, \(O(V^{2})\) Floyd.
AC 记录：shortest_path。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V+E) BFS/0-1 BFS, O(V+E log(E+2)) Dijkstra,
/// O(V+VE) Bellman-Ford/negative-cycle search, O(V^3) Floyd, O(path length) recovery.
/// Space: O(V) BFS/0-1 BFS/signed-cycle routines, O(V+E) Dijkstra, O(V^2) Floyd.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
// Single-source routines require a nonempty graph and a valid source.
// Vertices and edge IDs must fit int; inputs are never modified.
/// @brief BFS on unweighted graph. @return (distances, predecessors).
inline std::pair<std::vector<int>, std::vector<int>>
bfs_unweighted(std::vector<std::vector<int>> &g, int src) {
int N = int(g.size());
assert(0 <= src && src < N);
const int INF = std::numeric_limits<int>::max();
std::vector<int> dis(N, INF);
std::vector<int> pre(N, -1);
dis[src] = 0;
pre[src] = src;
std::vector<int> que{src};
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (auto v : g[u])
if (dis[v] == INF) {
dis[v] = dis[u] + 1;
pre[v] = u;
que.push_back(v);
}
}
return {std::move(dis), std::move(pre)};
}
/// @brief Dijkstra for nonnegative integer weights. Unreachable/unrepresentable
/// distances use int64_t::max(); weights and sums must fit __int128.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
dijkstra(std::vector<std::vector<T>> &g, int src) {
int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
std::vector<int64_t> dis(N, INF);
std::vector<int> pre(N, -1);
std::priority_queue<std::pair<int64_t, int>,
std::vector<std::pair<int64_t, int>>, std::greater<>>
que;
que.emplace(dis[src] = 0, src);
pre[src] = src;
while (!que.empty()) {
auto [d, u] = que.top();
que.pop();
if (d > dis[u])
continue;
for (auto &[v, w] : g[u]) {
assert(w >= 0);
__int128 can = __int128(dis[u]) + __int128(w);
if (can < dis[v]) {
dis[v] = static_cast<int64_t>(can);
pre[v] = u;
que.emplace(dis[v], v);
}
}
}
return {std::move(dis), std::move(pre)};
}
/// @brief Shortest paths in a graph whose edge weights are 0 or 1.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
bfs01(const std::vector<std::vector<T>> &g, int src) {
const int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
std::vector<int64_t> dis(N, INF);
std::vector<int> pre(N, -1);
std::deque<int> que;
std::vector<unsigned char> settled(N);
dis[src] = 0;
pre[src] = src;
que.push_front(src);
while (!que.empty()) {
int u = que.front();
que.pop_front();
if (settled[u]) continue;
settled[u] = true;
for (const auto &[v, w1] : g[u]) {
assert(w1 == 0 || w1 == 1);
if (dis[v] <= dis[u] + w1) {
continue;
}
dis[v] = dis[u] + w1;
pre[v] = u;
if (w1 == 0) {
que.push_front(v);
} else {
que.push_back(v);
}
}
}
return {std::move(dis), std::move(pre)};
}
struct bellman_ford_result {
std::vector<int64_t> di1;
std::vector<int> prv;
std::vector<bool> neg;
};
/// @brief Return edge ids forming one negative directed cycle anywhere in the
/// graph, in traversal order, or an empty vector when no negative cycle exists.
/// Integer weights and intermediate arithmetic must fit __int128.
template <class Weight>
std::vector<int>
find_negative_cycle(int n,
const std::vector<std::tuple<int, int, Weight>> &es) {
assert(n >= 0);
std::vector<__int128> di1(n);
std::vector<int> pe(n, -1);
int cv = -1;
for (int ite = 0; ite < n; ite++) {
cv = -1;
for (int id = 0; id < int(es.size()); id++) {
auto [u1, to, w1] = es[id];
assert(0 <= u1 && u1 < n);
assert(0 <= to && to < n);
__int128 can = di1[u1] + __int128(w1);
if (can < di1[to]) {
di1[to] = can;
pe[to] = id;
cv = to;
}
}
if (cv == -1) return {};
}
if (cv == -1) {
return {};
}
for (int stp = 0; stp < n; stp++) {
int id = pe[cv];
assert(id != -1);
cv = std::get<0>(es[id]);
}
int src = cv;
std::vector<int> cyc;
do {
int id = pe[cv];
assert(id != -1);
cyc.push_back(id);
cv = std::get<0>(es[id]);
} while (cv != src);
std::reverse(cyc.begin(), cyc.end());
return cyc;
}
/// @brief Bellman-Ford with propagation from source-reachable negative cycles.
/// A negative-infinite vertex has distance numeric_limits<int64_t>::lowest().
/// Finite distances saturate to int64_t bounds; neg distinguishes negative
/// infinity from finite underflow. Integer intermediate sums must fit __int128
/// and remain below 2^120. Unreachable vertices have INF and predecessor -1.
template <class T>
bellman_ford_result bellman_ford(const std::vector<std::vector<T>> &g,
int src) {
const int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
const int64_t NIF = std::numeric_limits<int64_t>::lowest();
const __int128 WIF = __int128(1) << 120;
std::vector<__int128> wd(N, WIF);
std::vector<int> pre(N, -1);
std::vector<bool> neg(N);
wd[src] = 0;
pre[src] = src;
std::vector<int> active;
for (int u = 0; u < N; ++u)
if (!g[u].empty()) active.push_back(u);
for (int ite = 0; ite < N; ite++) {
bool upd = false;
for (int u : active) {
if (wd[u] == WIF) {
continue;
}
for (const auto &[v, w1] : g[u]) {
__int128 can = wd[u] + static_cast<__int128>(w1);
if (can >= wd[v]) {
continue;
}
wd[v] = can;
pre[v] = u;
upd = true;
if (ite == N - 1) {
neg[v] = true;
}
}
}
if (!upd) {
break;
}
}
std::vector<int> que;
for (int u = 0; u < N; u++) {
if (neg[u]) {
que.push_back(u);
}
}
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (const auto &[v, w1] : g[u]) {
(void)w1;
if (!neg[v]) {
neg[v] = true;
que.push_back(v);
}
}
}
std::vector<int64_t> dis(N, INF);
for (int u = 0; u < N; u++) {
if (neg[u] || wd[u] < __int128(NIF)) {
dis[u] = NIF;
} else if (wd[u] < WIF) {
dis[u] = wd[u] > __int128(INF)
? INF
: static_cast<int64_t>(wd[u]);
}
}
return {std::move(dis), std::move(pre), std::move(neg)};
}
/// @brief Recover a valid, source-reaching acyclic predecessor chain.
/// Do not call for unreachable or negative-infinite targets.
inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
std::vector<int> pth;
int cur = t;
while (cur != s) {
assert(cur >= 0);
pth.push_back(cur);
cur = pre[cur];
}
pth.push_back(s);
std::reverse(pth.begin(), pth.end());
return pth;
}
/// @brief All-pairs integer distances; numeric_limits<T>::max()/2 denotes
/// an absent edge and unreachable pairs. Finite distances must lie below that
/// sentinel and fit int64_t; the graph must have no negative cycle.
template <class T>
std::vector<std::vector<int64_t>> floyd(std::vector<std::vector<T>> &g) {
int N = int(g.size());
const int64_t INF = std::numeric_limits<T>::max() / 2;
std::vector<std::vector<int64_t>> f(N, std::vector<int64_t>(N, INF));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f[i][j] = g[i][j];
for (int i = 0; i < N; i++)
f[i][i] = std::min<int64_t>(f[i][i], 0);
for (int k = 0; k < N; k++) {
const auto &from_k = f[k];
for (int i = 0; i < N; i++) {
auto &row = f[i];
// Without a negative cycle, this entry does not change within the row.
const int64_t to_k = row[k];
if (to_k == INF) continue;
for (int j = 0; j < N; j++)
if (from_k[j] != INF) {
__int128 can = __int128(to_k) + from_k[j];
assert(can >= std::numeric_limits<int64_t>::lowest());
if (can < row[j]) {
row[j] = static_cast<int64_t>(can);
}
}
}
}
return f;
}
} // namespace noya
// NOYA_SHORTEST_PATH_HPP
#ifndef NOYA_SHORTEST_PATH_HPP
#define NOYA_SHORTEST_PATH_HPP 1
/// @complexity Time: O(V+E) BFS/0-1 BFS, O(V+E log(E+2)) Dijkstra,
/// O(V+VE) Bellman-Ford/negative-cycle search, O(V^3) Floyd, O(path length) recovery.
/// Space: O(V) BFS/0-1 BFS/signed-cycle routines, O(V+E) Dijkstra, O(V^2) Floyd.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
// Single-source routines require a nonempty graph and a valid source.
// Vertices and edge IDs must fit int; inputs are never modified.
/// @brief BFS on unweighted graph. @return (distances, predecessors).
inline std::pair<std::vector<int>, std::vector<int>>
bfs_unweighted(std::vector<std::vector<int>> &g, int src) {
int N = int(g.size());
assert(0 <= src && src < N);
const int INF = std::numeric_limits<int>::max();
std::vector<int> dis(N, INF);
std::vector<int> pre(N, -1);
dis[src] = 0;
pre[src] = src;
std::vector<int> que{src};
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (auto v : g[u])
if (dis[v] == INF) {
dis[v] = dis[u] + 1;
pre[v] = u;
que.push_back(v);
}
}
return {std::move(dis), std::move(pre)};
}
/// @brief Dijkstra for nonnegative integer weights. Unreachable/unrepresentable
/// distances use int64_t::max(); weights and sums must fit __int128.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
dijkstra(std::vector<std::vector<T>> &g, int src) {
int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
std::vector<int64_t> dis(N, INF);
std::vector<int> pre(N, -1);
std::priority_queue<std::pair<int64_t, int>,
std::vector<std::pair<int64_t, int>>, std::greater<>>
que;
que.emplace(dis[src] = 0, src);
pre[src] = src;
while (!que.empty()) {
auto [d, u] = que.top();
que.pop();
if (d > dis[u])
continue;
for (auto &[v, w] : g[u]) {
assert(w >= 0);
__int128 can = __int128(dis[u]) + __int128(w);
if (can < dis[v]) {
dis[v] = static_cast<int64_t>(can);
pre[v] = u;
que.emplace(dis[v], v);
}
}
}
return {std::move(dis), std::move(pre)};
}
/// @brief Shortest paths in a graph whose edge weights are 0 or 1.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
bfs01(const std::vector<std::vector<T>> &g, int src) {
const int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
std::vector<int64_t> dis(N, INF);
std::vector<int> pre(N, -1);
std::deque<int> que;
std::vector<unsigned char> settled(N);
dis[src] = 0;
pre[src] = src;
que.push_front(src);
while (!que.empty()) {
int u = que.front();
que.pop_front();
if (settled[u]) continue;
settled[u] = true;
for (const auto &[v, w1] : g[u]) {
assert(w1 == 0 || w1 == 1);
if (dis[v] <= dis[u] + w1) {
continue;
}
dis[v] = dis[u] + w1;
pre[v] = u;
if (w1 == 0) {
que.push_front(v);
} else {
que.push_back(v);
}
}
}
return {std::move(dis), std::move(pre)};
}
struct bellman_ford_result {
std::vector<int64_t> di1;
std::vector<int> prv;
std::vector<bool> neg;
};
/// @brief Return edge ids forming one negative directed cycle anywhere in the
/// graph, in traversal order, or an empty vector when no negative cycle exists.
/// Integer weights and intermediate arithmetic must fit __int128.
template <class Weight>
std::vector<int>
find_negative_cycle(int n,
const std::vector<std::tuple<int, int, Weight>> &es) {
assert(n >= 0);
std::vector<__int128> di1(n);
std::vector<int> pe(n, -1);
int cv = -1;
for (int ite = 0; ite < n; ite++) {
cv = -1;
for (int id = 0; id < int(es.size()); id++) {
auto [u1, to, w1] = es[id];
assert(0 <= u1 && u1 < n);
assert(0 <= to && to < n);
__int128 can = di1[u1] + __int128(w1);
if (can < di1[to]) {
di1[to] = can;
pe[to] = id;
cv = to;
}
}
if (cv == -1) return {};
}
if (cv == -1) {
return {};
}
for (int stp = 0; stp < n; stp++) {
int id = pe[cv];
assert(id != -1);
cv = std::get<0>(es[id]);
}
int src = cv;
std::vector<int> cyc;
do {
int id = pe[cv];
assert(id != -1);
cyc.push_back(id);
cv = std::get<0>(es[id]);
} while (cv != src);
std::reverse(cyc.begin(), cyc.end());
return cyc;
}
/// @brief Bellman-Ford with propagation from source-reachable negative cycles.
/// A negative-infinite vertex has distance numeric_limits<int64_t>::lowest().
/// Finite distances saturate to int64_t bounds; neg distinguishes negative
/// infinity from finite underflow. Integer intermediate sums must fit __int128
/// and remain below 2^120. Unreachable vertices have INF and predecessor -1.
template <class T>
bellman_ford_result bellman_ford(const std::vector<std::vector<T>> &g,
int src) {
const int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
const int64_t NIF = std::numeric_limits<int64_t>::lowest();
const __int128 WIF = __int128(1) << 120;
std::vector<__int128> wd(N, WIF);
std::vector<int> pre(N, -1);
std::vector<bool> neg(N);
wd[src] = 0;
pre[src] = src;
std::vector<int> active;
for (int u = 0; u < N; ++u)
if (!g[u].empty()) active.push_back(u);
for (int ite = 0; ite < N; ite++) {
bool upd = false;
for (int u : active) {
if (wd[u] == WIF) {
continue;
}
for (const auto &[v, w1] : g[u]) {
__int128 can = wd[u] + static_cast<__int128>(w1);
if (can >= wd[v]) {
continue;
}
wd[v] = can;
pre[v] = u;
upd = true;
if (ite == N - 1) {
neg[v] = true;
}
}
}
if (!upd) {
break;
}
}
std::vector<int> que;
for (int u = 0; u < N; u++) {
if (neg[u]) {
que.push_back(u);
}
}
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (const auto &[v, w1] : g[u]) {
(void)w1;
if (!neg[v]) {
neg[v] = true;
que.push_back(v);
}
}
}
std::vector<int64_t> dis(N, INF);
for (int u = 0; u < N; u++) {
if (neg[u] || wd[u] < __int128(NIF)) {
dis[u] = NIF;
} else if (wd[u] < WIF) {
dis[u] = wd[u] > __int128(INF)
? INF
: static_cast<int64_t>(wd[u]);
}
}
return {std::move(dis), std::move(pre), std::move(neg)};
}
/// @brief Recover a valid, source-reaching acyclic predecessor chain.
/// Do not call for unreachable or negative-infinite targets.
inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
std::vector<int> pth;
int cur = t;
while (cur != s) {
assert(cur >= 0);
pth.push_back(cur);
cur = pre[cur];
}
pth.push_back(s);
std::reverse(pth.begin(), pth.end());
return pth;
}
/// @brief All-pairs integer distances; numeric_limits<T>::max()/2 denotes
/// an absent edge and unreachable pairs. Finite distances must lie below that
/// sentinel and fit int64_t; the graph must have no negative cycle.
template <class T>
std::vector<std::vector<int64_t>> floyd(std::vector<std::vector<T>> &g) {
int N = int(g.size());
const int64_t INF = std::numeric_limits<T>::max() / 2;
std::vector<std::vector<int64_t>> f(N, std::vector<int64_t>(N, INF));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f[i][j] = g[i][j];
for (int i = 0; i < N; i++)
f[i][i] = std::min<int64_t>(f[i][i], 0);
for (int k = 0; k < N; k++) {
const auto &from_k = f[k];
for (int i = 0; i < N; i++) {
auto &row = f[i];
// Without a negative cycle, this entry does not change within the row.
const int64_t to_k = row[k];
if (to_k == INF) continue;
for (int j = 0; j < N; j++)
if (from_k[j] != INF) {
__int128 can = __int128(to_k) + from_k[j];
assert(can >= std::numeric_limits<int64_t>::lowest());
if (can < row[j]) {
row[j] = static_cast<int64_t>(can);
}
}
}
}
return f;
}
} // namespace noya
#endif // NOYA_SHORTEST_PATH_HPP
/// @complexity Time: O(V+E) BFS/0-1 BFS, O(V+E log(E+2)) Dijkstra,
/// O(V+VE) Bellman-Ford/negative-cycle search, O(V^3) Floyd, O(path length) recovery.
/// Space: O(V) BFS/0-1 BFS/signed-cycle routines, O(V+E) Dijkstra, O(V^2) Floyd.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
// Single-source routines require a nonempty graph and a valid source.
// Vertices and edge IDs must fit int; inputs are never modified.
/// @brief BFS on unweighted graph. @return (distances, predecessors).
inline std::pair<std::vector<int>, std::vector<int>>
bfs_unweighted(std::vector<std::vector<int>> &g, int src) {
int N = int(g.size());
assert(0 <= src && src < N);
const int INF = std::numeric_limits<int>::max();
std::vector<int> dis(N, INF);
std::vector<int> pre(N, -1);
dis[src] = 0;
pre[src] = src;
std::vector<int> que{src};
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (auto v : g[u])
if (dis[v] == INF) {
dis[v] = dis[u] + 1;
pre[v] = u;
que.push_back(v);
}
}
return {std::move(dis), std::move(pre)};
}
/// @brief Dijkstra for nonnegative integer weights. Unreachable/unrepresentable
/// distances use int64_t::max(); weights and sums must fit __int128.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
dijkstra(std::vector<std::vector<T>> &g, int src) {
int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
std::vector<int64_t> dis(N, INF);
std::vector<int> pre(N, -1);
std::priority_queue<std::pair<int64_t, int>,
std::vector<std::pair<int64_t, int>>, std::greater<>>
que;
que.emplace(dis[src] = 0, src);
pre[src] = src;
while (!que.empty()) {
auto [d, u] = que.top();
que.pop();
if (d > dis[u])
continue;
for (auto &[v, w] : g[u]) {
assert(w >= 0);
__int128 can = __int128(dis[u]) + __int128(w);
if (can < dis[v]) {
dis[v] = static_cast<int64_t>(can);
pre[v] = u;
que.emplace(dis[v], v);
}
}
}
return {std::move(dis), std::move(pre)};
}
/// @brief Shortest paths in a graph whose edge weights are 0 or 1.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
bfs01(const std::vector<std::vector<T>> &g, int src) {
const int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
std::vector<int64_t> dis(N, INF);
std::vector<int> pre(N, -1);
std::deque<int> que;
std::vector<unsigned char> settled(N);
dis[src] = 0;
pre[src] = src;
que.push_front(src);
while (!que.empty()) {
int u = que.front();
que.pop_front();
if (settled[u]) continue;
settled[u] = true;
for (const auto &[v, w1] : g[u]) {
assert(w1 == 0 || w1 == 1);
if (dis[v] <= dis[u] + w1) {
continue;
}
dis[v] = dis[u] + w1;
pre[v] = u;
if (w1 == 0) {
que.push_front(v);
} else {
que.push_back(v);
}
}
}
return {std::move(dis), std::move(pre)};
}
struct bellman_ford_result {
std::vector<int64_t> di1;
std::vector<int> prv;
std::vector<bool> neg;
};
/// @brief Return edge ids forming one negative directed cycle anywhere in the
/// graph, in traversal order, or an empty vector when no negative cycle exists.
/// Integer weights and intermediate arithmetic must fit __int128.
template <class Weight>
std::vector<int>
find_negative_cycle(int n,
const std::vector<std::tuple<int, int, Weight>> &es) {
assert(n >= 0);
std::vector<__int128> di1(n);
std::vector<int> pe(n, -1);
int cv = -1;
for (int ite = 0; ite < n; ite++) {
cv = -1;
for (int id = 0; id < int(es.size()); id++) {
auto [u1, to, w1] = es[id];
assert(0 <= u1 && u1 < n);
assert(0 <= to && to < n);
__int128 can = di1[u1] + __int128(w1);
if (can < di1[to]) {
di1[to] = can;
pe[to] = id;
cv = to;
}
}
if (cv == -1) return {};
}
if (cv == -1) {
return {};
}
for (int stp = 0; stp < n; stp++) {
int id = pe[cv];
assert(id != -1);
cv = std::get<0>(es[id]);
}
int src = cv;
std::vector<int> cyc;
do {
int id = pe[cv];
assert(id != -1);
cyc.push_back(id);
cv = std::get<0>(es[id]);
} while (cv != src);
std::reverse(cyc.begin(), cyc.end());
return cyc;
}
/// @brief Bellman-Ford with propagation from source-reachable negative cycles.
/// A negative-infinite vertex has distance numeric_limits<int64_t>::lowest().
/// Finite distances saturate to int64_t bounds; neg distinguishes negative
/// infinity from finite underflow. Integer intermediate sums must fit __int128
/// and remain below 2^120. Unreachable vertices have INF and predecessor -1.
template <class T>
bellman_ford_result bellman_ford(const std::vector<std::vector<T>> &g,
int src) {
const int N = int(g.size());
assert(0 <= src && src < N);
const int64_t INF = std::numeric_limits<int64_t>::max();
const int64_t NIF = std::numeric_limits<int64_t>::lowest();
const __int128 WIF = __int128(1) << 120;
std::vector<__int128> wd(N, WIF);
std::vector<int> pre(N, -1);
std::vector<bool> neg(N);
wd[src] = 0;
pre[src] = src;
std::vector<int> active;
for (int u = 0; u < N; ++u)
if (!g[u].empty()) active.push_back(u);
for (int ite = 0; ite < N; ite++) {
bool upd = false;
for (int u : active) {
if (wd[u] == WIF) {
continue;
}
for (const auto &[v, w1] : g[u]) {
__int128 can = wd[u] + static_cast<__int128>(w1);
if (can >= wd[v]) {
continue;
}
wd[v] = can;
pre[v] = u;
upd = true;
if (ite == N - 1) {
neg[v] = true;
}
}
}
if (!upd) {
break;
}
}
std::vector<int> que;
for (int u = 0; u < N; u++) {
if (neg[u]) {
que.push_back(u);
}
}
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (const auto &[v, w1] : g[u]) {
(void)w1;
if (!neg[v]) {
neg[v] = true;
que.push_back(v);
}
}
}
std::vector<int64_t> dis(N, INF);
for (int u = 0; u < N; u++) {
if (neg[u] || wd[u] < __int128(NIF)) {
dis[u] = NIF;
} else if (wd[u] < WIF) {
dis[u] = wd[u] > __int128(INF)
? INF
: static_cast<int64_t>(wd[u]);
}
}
return {std::move(dis), std::move(pre), std::move(neg)};
}
/// @brief Recover a valid, source-reaching acyclic predecessor chain.
/// Do not call for unreachable or negative-infinite targets.
inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
std::vector<int> pth;
int cur = t;
while (cur != s) {
assert(cur >= 0);
pth.push_back(cur);
cur = pre[cur];
}
pth.push_back(s);
std::reverse(pth.begin(), pth.end());
return pth;
}
/// @brief All-pairs integer distances; numeric_limits<T>::max()/2 denotes
/// an absent edge and unreachable pairs. Finite distances must lie below that
/// sentinel and fit int64_t; the graph must have no negative cycle.
template <class T>
std::vector<std::vector<int64_t>> floyd(std::vector<std::vector<T>> &g) {
int N = int(g.size());
const int64_t INF = std::numeric_limits<T>::max() / 2;
std::vector<std::vector<int64_t>> f(N, std::vector<int64_t>(N, INF));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f[i][j] = g[i][j];
for (int i = 0; i < N; i++)
f[i][i] = std::min<int64_t>(f[i][i], 0);
for (int k = 0; k < N; k++) {
const auto &from_k = f[k];
for (int i = 0; i < N; i++) {
auto &row = f[i];
// Without a negative cycle, this entry does not change within the row.
const int64_t to_k = row[k];
if (to_k == INF) continue;
for (int j = 0; j < N; j++)
if (from_k[j] != INF) {
__int128 can = __int128(to_k) + from_k[j];
assert(can >= std::numeric_limits<int64_t>::lowest());
if (can < row[j]) {
row[j] = static_cast<int64_t>(can);
}
}
}
}
return f;
}
} // namespace noya
// NOYA_SHORTEST_PATH_HPP