test/simple-wf1.test.cpp

View this file on GitHub
Last update: 2022-12-07 03:14:09+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C"

#include "../src/graph/simple/wf.hpp"
#include "../src/graph/Read-Weighted-Graph.hpp"

#include <iostream>

int main() {
    int n, m; std::cin >> n >> m;
    const long long inf = 1e15;
    auto G = zawa::wf<long long>(zawa::read_weighted_graph<long long>(n, m, false, false), inf);
    bool neg = false;
    for (int i = 0 ; i < n ; i++) {
        neg |= G[i][i] < 0;
    }
    if (neg) {
        std::cout << "NEGATIVE CYCLE" << std::endl;
    }
    else {
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < n ; j++) {
                if (G[i][j] > 1e12) {
                    std::cout << "INF";
                }
                else {
                    std::cout << G[i][j];
                }
                std::cout << (j == n - 1 ? '\n' : ' ');
            }
        }
    }
}

#line 1 "test/simple-wf1.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C"

#line 2 "src/graph/simple/wf.hpp"

#include <vector>
#include <utility>
#include <limits>
#include <algorithm>

namespace zawa {

template <class cost_type>
std::vector<std::vector<cost_type>> wf(const std::vector<std::vector<std::pair<int, cost_type>>>& G, cost_type inf = std::numeric_limits<cost_type>::max() / 3) {
    std::vector res(G.size(), std::vector(G.size(), inf));
    for (std::size_t i = 0 ; i < G.size() ; i++) {
        res[i][i] = 0;
    }
    for (std::size_t i = 0 ; i < G.size() ; i++) {
        for (auto [x, w] : G[i]) {
            res[i][x] = std::min(res[i][x], w);
        }
    }
    for (std::size_t k = 0 ; k < G.size() ; k++) {
        for (std::size_t i = 0 ; i < G.size() ; i++) {
            for (std::size_t j = 0 ; j < G.size() ; j++) {
                res[i][j] = std::min(res[i][j], res[i][k] + res[k][j]);
            }
        }
    }
    return res;
}

} // namespace zawa
#line 2 "src/graph/Read-Weighted-Graph.hpp"

#line 5 "src/graph/Read-Weighted-Graph.hpp"
#include <iostream>

namespace zawa {

template <typename T>
std::vector<std::vector<std::pair<int, T>>> read_weighted_graph(int n, int m, bool undirect = true, bool minus = true) {
    std::vector<std::vector<std::pair<int, T>>> res(n, std::vector(0, std::pair<int, T>()));
    for (int _ = 0 ; _ < m ; _++) {
        int u, v; std::cin >> u >> v;
        T c; std::cin >> c;
        res[u - minus].emplace_back(v - minus, c);
        if (undirect) {
            res[v - minus].emplace_back(u - minus, c);
        }
    }
    return res;
}

template <typename T>
std::vector<std::vector<std::pair<int, T>>> read_weighted_tree(int n, bool undirect = true) {
    return read_weighted_graph<T>(n, n - 1, undirect);
}

} // namespace zawa
#line 5 "test/simple-wf1.test.cpp"

#line 7 "test/simple-wf1.test.cpp"

int main() {
    int n, m; std::cin >> n >> m;
    const long long inf = 1e15;
    auto G = zawa::wf<long long>(zawa::read_weighted_graph<long long>(n, m, false, false), inf);
    bool neg = false;
    for (int i = 0 ; i < n ; i++) {
        neg |= G[i][i] < 0;
    }
    if (neg) {
        std::cout << "NEGATIVE CYCLE" << std::endl;
    }
    else {
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j < n ; j++) {
                if (G[i][j] > 1e12) {
                    std::cout << "INF";
                }
                else {
                    std::cout << G[i][j];
                }
                std::cout << (j == n - 1 ? '\n' : ' ');
            }
        }
    }
}