test/AOJ/GRL_1_B.test.cpp
Depends on
Code
#define PROBLEM \
"https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"
#include <bits/stdc++.h>
#include "library/graph/WeightedGraph.hpp"
#include "library/graph/shortest_path/BellmanFord.hpp"
using ll = long long;
int main() {
int n, m, s;
std::cin >> n >> m >> s;
WeightedGraph<ll> g(n, m, true, 0);
auto [d, pre] = bellman_ford(g, s);
for (const auto &p : d)
if (!p) {
std::cout << "NEGATIVE CYCLE\n";
return 0;
}
for (int i = 0; i < n; i++)
if (~pre[i] || i == s)
std::cout << d[i].value() << "\n";
else
std::cout << "INF\n";
}
#line 1 "test/AOJ/GRL_1_B.test.cpp"
#define PROBLEM \
"https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"
#include <bits/stdc++.h>
#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
WeightedEdge() = default;
WeightedEdge(int from, int to, T weight)
: from(from), to(to), weight(weight) {}
int from, to;
T weight;
operator int() const { return to; }
};
template <typename T> struct WeightedGraph {
int n;
using weight_type = T;
using edge_type = WeightedEdge<T>;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
WeightedGraph *g;
int l, r;
public:
OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const WeightedGraph *g;
int l, r;
public:
ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
: g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to, T weight) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to, weight);
in_deg[from + 1]++;
}
void add_edge(int u, int v, T weight) {
add_arc(u, v, weight);
add_arc(v, u, weight);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
T weight;
std::cin >> weight;
if (directed)
add_arc(u, v, weight);
else
add_edge(u, v, weight);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __DEBUG
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << "(" << edges[i].to << "," << edges[i].weight
<< ")";
std::cerr << "\n";
}
}
};
#line 1 "library/graph/shortest_path/BellmanFord.hpp"
// s からの最短距離が定まるなら最短距離, 無限に小さく出来るなら std::nullopt
// そもそも到達出来ない場合は pre が -1 になっている
template <typename WG, typename T = typename WG::weight_type>
std::pair<std::vector<std::optional<T>>, std::vector<int>>
bellman_ford(const WG &g, int s = 0) {
assert(g.is_prepared());
int n = g.n;
static constexpr T INF = std::numeric_limits<T>::max() / 2;
std::vector<T> d(n, INF);
std::vector<int> pre(n, -1);
d[s] = 0;
for (int _ = 0; _ < n; _++) {
bool update = false;
for (int v = 0; v < n; v++)
if (d[v] < INF)
for (const auto &e : g[v])
if (d[e.to] > d[v] + e.weight) {
d[e.to] = d[v] + e.weight;
pre[e.to] = v;
update = true;
}
if (!update) {
std::vector<std::optional<T>> d_(n);
for (int i = 0; i < n; i++)
d_[i] = d[i];
return {d_, pre};
}
}
auto now_d = d;
for (int v = 0; v < n; v++)
if (d[v] < INF)
for (const auto &e : g[v])
if (d[e.to] > d[v] + e.weight)
d[e.to] = d[v] + e.weight;
for (int _ = 1; _ < n; _++)
for (int v = 0; v < n; v++)
if (d[v] < now_d[v])
for (const auto &e : g[v])
if (d[e.to] > d[v] + e.weight)
d[e.to] = d[v] + e.weight;
std::vector<std::optional<T>> res(n);
for (int v = 0; v < n; v++)
if (now_d[v] == d[v])
res[v] = d[v];
else
res[v] = std::nullopt;
return {res, pre};
}
#line 7 "test/AOJ/GRL_1_B.test.cpp"
using ll = long long;
int main() {
int n, m, s;
std::cin >> n >> m >> s;
WeightedGraph<ll> g(n, m, true, 0);
auto [d, pre] = bellman_ford(g, s);
for (const auto &p : d)
if (!p) {
std::cout << "NEGATIVE CYCLE\n";
return 0;
}
for (int i = 0; i < n; i++)
if (~pre[i] || i == s)
std::cout << d[i].value() << "\n";
else
std::cout << "INF\n";
}
Back to top page
build/pch/stdc++.hpp