test/aoj/GRL_1_C.test.cpp

View this file on GitHub
Last update: 2021-01-31 19:19:57+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

Depends on

Code

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

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

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

#include "../../src/FloydWarshall.hpp"

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

int main() {

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

    vector<vector<lint>> edges(N, vector<lint>(N, LINF));
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edges[u][v] = c;
    }

    auto cost = FloydWarshall(edges);

    for (int i = 0; i < N; i++) {
        if (cost[i][i] < 0) {
            cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }

    for (const auto &row : cost) {
        for (const auto &e : row) {
            cout << (e != LINF ? to_string(e) : "INF");
            if (&e != &row.back()) cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}

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

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

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

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

#line 2 "src/FloydWarshall.hpp"

#include <cassert>
#line 5 "src/FloydWarshall.hpp"

#line 2 "src/chmin.hpp"

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

using namespace std;

template<class T>
vector<vector<T>> FloydWarshall(const vector<vector<T>> &in, const T diag = T{}) {

    const int N = in.size();
    assert(N == (int)in[0].size());
    const T inf = in[0][0];

    auto d = in;
    for (int i = 0; i < N; i++) d[i][i] = diag;
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (d[i][k] < inf && d[k][j] < inf) chmin(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    return d;
}
#line 14 "test/aoj/GRL_1_C.test.cpp"

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

int main() {

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

    vector<vector<lint>> edges(N, vector<lint>(N, LINF));
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edges[u][v] = c;
    }

    auto cost = FloydWarshall(edges);

    for (int i = 0; i < N; i++) {
        if (cost[i][i] < 0) {
            cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }

    for (const auto &row : cost) {
        for (const auto &e : row) {
            cout << (e != LINF ? to_string(e) : "INF");
            if (&e != &row.back()) cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}