This documentation is automatically generated by online-judge-tools/verification-helper
#include "graph/bellman_ford.hpp"bellman_ford<T> bf(n): 頂点数 n、辺の重みの型 T。add_edge(from, to, w): 重み w の有向辺を追加する。solve(s): 頂点 s を始点として最短路を求める。dist(v): s から v への最短距離。到達不能なら std::numeric_limits<T>::max()、下に有界でなければ std::numeric_limits<T>::lowest()。prev(v): 最短路における v の直前の頂点。s と到達不能な頂点では -1。reachable(v): s から v に到達可能か。unbounded(v): s から負閉路を通って v に到達可能か。has_negative_cycle(): s から到達可能な負閉路があるか。path(t): s から t への最短路の頂点列。到達不能か下に有界でなければ空。| $N \cdot \max | w | $ が T の範囲に収まる |
solve: $\mathcal{O}(NM)$has_negative_cycle, path: $\mathcal{O}(N)$AOJ GRL_1_B - Single Source Shortest Path (Negative Edges)(問題)
#include <iostream>
#include "graph/bellman_ford.hpp"
int main() {
int n, m, r;
std::cin >> n >> m >> r;
bellman_ford<long long> bf(n);
for (int i = 0; i < m; i++) {
int s, t;
long long d;
std::cin >> s >> t >> d;
bf.add_edge(s, t, d);
}
bf.solve(r);
if (bf.has_negative_cycle()) {
std::cout << "NEGATIVE CYCLE\n";
return 0;
}
for (int v = 0; v < n; v++) {
if (bf.reachable(v)) {
std::cout << bf.dist(v) << '\n';
} else {
std::cout << "INF\n";
}
}
}
#pragma once
#include <algorithm>
#include <cassert>
#include <limits>
#include <tuple>
#include <vector>
template <class T> struct bellman_ford {
public:
bellman_ford() : bellman_ford(0) {
}
explicit bellman_ford(int n) : _n(n), _dist(n, inf), _prev(n, -1) {
}
void add_edge(int from, int to, T w) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
edges.emplace_back(from, to, w);
}
void solve(int s) {
assert(0 <= s && s < _n);
_dist.assign(_n, inf);
_prev.assign(_n, -1);
_dist[s] = 0;
for (int i = 0; i < _n - 1; i++) {
bool updated = false;
for (auto [u, v, w] : edges) {
if (_dist[u] == inf) continue;
if (_dist[u] + w < _dist[v]) {
_dist[v] = _dist[u] + w;
_prev[v] = u;
updated = true;
}
}
if (!updated) return;
}
for (int i = 0; i < _n; i++) {
bool updated = false;
for (auto [u, v, w] : edges) {
if (_dist[u] == inf || _dist[v] == ninf) continue;
if (_dist[u] == ninf || _dist[u] + w < _dist[v]) {
_dist[v] = ninf;
updated = true;
}
}
if (!updated) return;
}
}
T dist(int v) const {
assert(0 <= v && v < _n);
return _dist[v];
}
int prev(int v) const {
assert(0 <= v && v < _n);
return _prev[v];
}
bool reachable(int v) const {
assert(0 <= v && v < _n);
return _dist[v] != inf;
}
bool unbounded(int v) const {
assert(0 <= v && v < _n);
return _dist[v] == ninf;
}
bool has_negative_cycle() const {
return std::ranges::find(_dist, ninf) != _dist.end();
}
std::vector<int> path(int t) const {
assert(0 <= t && t < _n);
if (_dist[t] == inf || _dist[t] == ninf) return {};
std::vector<int> res;
for (int v = t; v != -1; v = _prev[v]) res.push_back(v);
std::ranges::reverse(res);
return res;
}
private:
static constexpr T inf = std::numeric_limits<T>::max();
static constexpr T ninf = std::numeric_limits<T>::lowest();
int _n;
std::vector<std::tuple<int, int, T>> edges;
std::vector<T> _dist;
std::vector<int> _prev;
};#line 2 "graph/bellman_ford.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <tuple>
#include <vector>
template <class T> struct bellman_ford {
public:
bellman_ford() : bellman_ford(0) {
}
explicit bellman_ford(int n) : _n(n), _dist(n, inf), _prev(n, -1) {
}
void add_edge(int from, int to, T w) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
edges.emplace_back(from, to, w);
}
void solve(int s) {
assert(0 <= s && s < _n);
_dist.assign(_n, inf);
_prev.assign(_n, -1);
_dist[s] = 0;
for (int i = 0; i < _n - 1; i++) {
bool updated = false;
for (auto [u, v, w] : edges) {
if (_dist[u] == inf) continue;
if (_dist[u] + w < _dist[v]) {
_dist[v] = _dist[u] + w;
_prev[v] = u;
updated = true;
}
}
if (!updated) return;
}
for (int i = 0; i < _n; i++) {
bool updated = false;
for (auto [u, v, w] : edges) {
if (_dist[u] == inf || _dist[v] == ninf) continue;
if (_dist[u] == ninf || _dist[u] + w < _dist[v]) {
_dist[v] = ninf;
updated = true;
}
}
if (!updated) return;
}
}
T dist(int v) const {
assert(0 <= v && v < _n);
return _dist[v];
}
int prev(int v) const {
assert(0 <= v && v < _n);
return _prev[v];
}
bool reachable(int v) const {
assert(0 <= v && v < _n);
return _dist[v] != inf;
}
bool unbounded(int v) const {
assert(0 <= v && v < _n);
return _dist[v] == ninf;
}
bool has_negative_cycle() const {
return std::ranges::find(_dist, ninf) != _dist.end();
}
std::vector<int> path(int t) const {
assert(0 <= t && t < _n);
if (_dist[t] == inf || _dist[t] == ninf) return {};
std::vector<int> res;
for (int v = t; v != -1; v = _prev[v]) res.push_back(v);
std::ranges::reverse(res);
return res;
}
private:
static constexpr T inf = std::numeric_limits<T>::max();
static constexpr T ninf = std::numeric_limits<T>::lowest();
int _n;
std::vector<std::tuple<int, int, T>> edges;
std::vector<T> _dist;
std::vector<int> _prev;
};