test/aoj/GRL_1_B.test.cpp

View this file on GitHub
Last update: 2021-02-22 09:25:55+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr lint LINF = 1LL << 60;

#include "../../src/BellmanFord.hpp"

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N, M, s;
    cin >> N >> M >> s;

    vector<Edge<lint>> edges;
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edges.emplace_back(u, v, c);
    }

    auto costs = BellmanFord(edges, N, s);
    if (any_of(costs.begin(), costs.end(), [&](auto &c) { return c < -LINF; })) {
        cout << "NEGATIVE CYCLE\n";
        return 0;
    }
    for (const auto &cost : costs) {
        cout << (cost < LINF ? to_string(cost) : "INF") << '\n';
    }

    return 0;
}

#line 1 "test/aoj/GRL_1_B.test.cpp"

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr lint LINF = 1LL << 60;

#line 2 "src/BellmanFord.hpp"

#line 5 "src/BellmanFord.hpp"

#line 2 "src/chmin.hpp"

template<class T>
inline bool chmin(T &a, const T b) { return a > b && (a = b, true); }
#line 2 "src/Edge.hpp"

template<class T>
struct Edge {
    int from{}, to{};
    T cost;
    Edge() = default;
    Edge(int to, T cost) : to(to), cost(move(cost)) {}
    Edge(int from, int to, T cost) : from(from), to(to), cost(move(cost)) {}
    bool operator>(const Edge &r) const { return this->cost > r.cost; }
};
#line 8 "src/BellmanFord.hpp"

using namespace std;

template<class T>
vector<T> BellmanFord(const vector<Edge<T>> &edges, const int V, const int st) {

    const T inf = numeric_limits<T>::max() / 2;
    vector<T> cost(V, inf);
    cost[st] = 0;
    for (int i = 0; i < V - 1; i++) {
        for (const auto &e : edges) {
            if (cost[e.from] == inf) continue;
            chmin(cost[e.to], cost[e.from] + e.cost);
        }
    }

    for (int i = 0; i < V; i++) {
        for (const auto &e : edges) { // finding negative loop
            if (cost[e.from] == inf) continue;
            if (cost[e.from] == -inf) cost[e.to] = -inf; // src is nloop -> dst is nloop
            else if (cost[e.to] > cost[e.from] + e.cost) cost[e.to] = -inf; // chmin is possible -> nloop
        }
    }

    return cost;
}
#line 15 "test/aoj/GRL_1_B.test.cpp"

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N, M, s;
    cin >> N >> M >> s;

    vector<Edge<lint>> edges;
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edges.emplace_back(u, v, c);
    }

    auto costs = BellmanFord(edges, N, s);
    if (any_of(costs.begin(), costs.end(), [&](auto &c) { return c < -LINF; })) {
        cout << "NEGATIVE CYCLE\n";
        return 0;
    }
    for (const auto &cost : costs) {
        cout << (cost < LINF ? to_string(cost) : "INF") << '\n';
    }

    return 0;
}