C++ Library for Competitive Programming
/*
* @title グラフ/最短路問題/Bellman–Ford 法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B
*/
#include <iostream>
#include <vector>
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/shortest_path/bellman-ford.hpp"
int main() {
int v, e, r;
std::cin >> v >> e >> r;
std::vector<std::vector<emthrm::Edge<long long>>> graph(v);
while (e--) {
int s, t, d;
std::cin >> s >> t >> d;
graph[s].emplace_back(s, t, d);
}
emthrm::BellmanFord<long long> bellman_ford(graph);
if (bellman_ford.has_negative_cycle(r)) {
std::cout << "NEGATIVE CYCLE\n";
return 0;
}
for (int i = 0; i < v; ++i) {
if (bellman_ford.dist[i] == bellman_ford.inf) {
std::cout << "INF\n";
} else {
std::cout << bellman_ford.dist[i] << '\n';
}
}
return 0;
}
#line 1 "test/graph/shortest_path/bellman-ford.test.cpp"
/*
* @title グラフ/最短路問題/Bellman–Ford 法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B
*/
#include <iostream>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/shortest_path/bellman-ford.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#line 8 "include/emthrm/graph/shortest_path/bellman-ford.hpp"
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/shortest_path/bellman-ford.hpp"
namespace emthrm {
template <typename CostType>
struct BellmanFord {
const CostType inf;
std::vector<CostType> dist;
BellmanFord(const std::vector<std::vector<Edge<CostType>>>& graph,
const CostType inf = std::numeric_limits<CostType>::max())
: inf(inf), is_built(false), graph(graph) {}
bool has_negative_cycle(const int s) {
is_built = true;
const int n = graph.size();
dist.assign(n, inf);
dist[s] = 0;
prev.assign(n, -1);
for (int step = 0; step < n; ++step) {
bool is_updated = false;
for (int i = 0; i < n; ++i) {
if (dist[i] == inf) continue;
for (const Edge<CostType>& e : graph[i]) {
if (dist[e.dst] > dist[i] + e.cost) {
dist[e.dst] = dist[i] + e.cost;
prev[e.dst] = i;
is_updated = true;
}
}
}
if (!is_updated) return false;
}
return true;
}
std::vector<int> build_path(int t) const {
assert(is_built);
std::vector<int> res;
for (; t != -1; t = prev[t]) {
res.emplace_back(t);
}
std::reverse(res.begin(), res.end());
return res;
}
private:
bool is_built;
std::vector<int> prev;
std::vector<std::vector<Edge<CostType>>> graph;
};
} // namespace emthrm
#line 12 "test/graph/shortest_path/bellman-ford.test.cpp"
int main() {
int v, e, r;
std::cin >> v >> e >> r;
std::vector<std::vector<emthrm::Edge<long long>>> graph(v);
while (e--) {
int s, t, d;
std::cin >> s >> t >> d;
graph[s].emplace_back(s, t, d);
}
emthrm::BellmanFord<long long> bellman_ford(graph);
if (bellman_ford.has_negative_cycle(r)) {
std::cout << "NEGATIVE CYCLE\n";
return 0;
}
for (int i = 0; i < v; ++i) {
if (bellman_ford.dist[i] == bellman_ford.inf) {
std::cout << "INF\n";
} else {
std::cout << bellman_ford.dist[i] << '\n';
}
}
return 0;
}