library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/bellman_ford.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "graph/bellman_ford.hpp"
int main() {
    std::mt19937 rng(20261029);
    const long long inf = 1LL << 50;
    for (int trial = 0; trial < 3000; trial++) {
        int n = 1 + rng() % 7;
        int m = rng() % 13;
        std::vector<std::vector<long long>> w(n, std::vector<long long>(n, inf));
        bellman_ford<long long> bf(n);
        for (int i = 0; i < m; i++) {
            int u = rng() % n, v = rng() % n;
            long long c = (long long)(rng() % 9) - 3;
            w[u][v] = std::min(w[u][v], c);
            bf.add_edge(u, v, c);
        }
        std::vector<std::vector<bool>> reach(n, std::vector<bool>(n, false));
        std::vector<std::vector<long long>> d(n, std::vector<long long>(n, inf));
        for (int i = 0; i < n; i++) {
            reach[i][i] = true;
            d[i][i] = 0;
            for (int j = 0; j < n; j++) {
                if (w[i][j] != inf) {
                    reach[i][j] = true;
                    d[i][j] = std::min(d[i][j], w[i][j]);
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
                    if (d[i][k] != inf && d[k][j] != inf) d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int s = rng() % n;
        bf.solve(s);
        bool any_negative = false;
        for (int v = 0; v < n; v++) {
            bool unb = false;
            for (int k = 0; k < n; k++) {
                if (reach[s][k] && d[k][k] < 0 && reach[k][v]) unb = true;
            }
            any_negative = any_negative || unb;
            assert(bf.reachable(v) == reach[s][v]);
            assert(bf.unbounded(v) == unb);
            if (!reach[s][v]) {
                assert(bf.dist(v) == std::numeric_limits<long long>::max());
                assert(bf.prev(v) == -1);
                assert(bf.path(v).empty());
            } else if (unb) {
                assert(bf.dist(v) == std::numeric_limits<long long>::lowest());
                assert(bf.path(v).empty());
            } else {
                assert(bf.dist(v) == d[s][v]);
                std::vector<int> p = bf.path(v);
                assert(!p.empty() && p.front() == s && p.back() == v);
                long long total = 0;
                for (int i = 0; i + 1 < int(p.size()); i++) {
                    assert(w[p[i]][p[i + 1]] != inf);
                    total += w[p[i]][p[i + 1]];
                }
                assert(total == d[s][v]);
                assert(bf.prev(v) == (v == s ? -1 : p[p.size() - 2]));
            }
        }
        assert(bf.has_negative_cycle() == any_negative);
    }
    bellman_ford<double> bd(3);
    bd.add_edge(0, 1, 0.5);
    bd.add_edge(1, 2, -1.5);
    bd.solve(0);
    assert(bd.dist(2) == -1.0);
    assert(!bd.has_negative_cycle());
    std::cout << "Hello World\n";
}
#line 1 "test/unit/bellman_ford.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#line 4 "graph/bellman_ford.hpp"
#include <limits>
#include <tuple>
#line 7 "graph/bellman_ford.hpp"
template <class T> struct bellman_ford {
public:
    bellman_ford() : bellman_ford(0) {
    }
    explicit bellman_ford(int n) : _n(n), _dist(n, inf), _prev(n, -1) {
    }
    void add_edge(int from, int to, T w) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        edges.emplace_back(from, to, w);
    }
    void solve(int s) {
        assert(0 <= s && s < _n);
        _dist.assign(_n, inf);
        _prev.assign(_n, -1);
        _dist[s] = 0;
        for (int i = 0; i < _n - 1; i++) {
            bool updated = false;
            for (auto [u, v, w] : edges) {
                if (_dist[u] == inf) continue;
                if (_dist[u] + w < _dist[v]) {
                    _dist[v] = _dist[u] + w;
                    _prev[v] = u;
                    updated = true;
                }
            }
            if (!updated) return;
        }
        for (int i = 0; i < _n; i++) {
            bool updated = false;
            for (auto [u, v, w] : edges) {
                if (_dist[u] == inf || _dist[v] == ninf) continue;
                if (_dist[u] == ninf || _dist[u] + w < _dist[v]) {
                    _dist[v] = ninf;
                    updated = true;
                }
            }
            if (!updated) return;
        }
    }
    T dist(int v) const {
        assert(0 <= v && v < _n);
        return _dist[v];
    }
    int prev(int v) const {
        assert(0 <= v && v < _n);
        return _prev[v];
    }
    bool reachable(int v) const {
        assert(0 <= v && v < _n);
        return _dist[v] != inf;
    }
    bool unbounded(int v) const {
        assert(0 <= v && v < _n);
        return _dist[v] == ninf;
    }
    bool has_negative_cycle() const {
        return std::ranges::find(_dist, ninf) != _dist.end();
    }
    std::vector<int> path(int t) const {
        assert(0 <= t && t < _n);
        if (_dist[t] == inf || _dist[t] == ninf) return {};
        std::vector<int> res;
        for (int v = t; v != -1; v = _prev[v]) res.push_back(v);
        std::ranges::reverse(res);
        return res;
    }

private:
    static constexpr T inf = std::numeric_limits<T>::max();
    static constexpr T ninf = std::numeric_limits<T>::lowest();
    int _n;
    std::vector<std::tuple<int, int, T>> edges;
    std::vector<T> _dist;
    std::vector<int> _prev;
};
#line 9 "test/unit/bellman_ford.test.cpp"
int main() {
    std::mt19937 rng(20261029);
    const long long inf = 1LL << 50;
    for (int trial = 0; trial < 3000; trial++) {
        int n = 1 + rng() % 7;
        int m = rng() % 13;
        std::vector<std::vector<long long>> w(n, std::vector<long long>(n, inf));
        bellman_ford<long long> bf(n);
        for (int i = 0; i < m; i++) {
            int u = rng() % n, v = rng() % n;
            long long c = (long long)(rng() % 9) - 3;
            w[u][v] = std::min(w[u][v], c);
            bf.add_edge(u, v, c);
        }
        std::vector<std::vector<bool>> reach(n, std::vector<bool>(n, false));
        std::vector<std::vector<long long>> d(n, std::vector<long long>(n, inf));
        for (int i = 0; i < n; i++) {
            reach[i][i] = true;
            d[i][i] = 0;
            for (int j = 0; j < n; j++) {
                if (w[i][j] != inf) {
                    reach[i][j] = true;
                    d[i][j] = std::min(d[i][j], w[i][j]);
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
                    if (d[i][k] != inf && d[k][j] != inf) d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int s = rng() % n;
        bf.solve(s);
        bool any_negative = false;
        for (int v = 0; v < n; v++) {
            bool unb = false;
            for (int k = 0; k < n; k++) {
                if (reach[s][k] && d[k][k] < 0 && reach[k][v]) unb = true;
            }
            any_negative = any_negative || unb;
            assert(bf.reachable(v) == reach[s][v]);
            assert(bf.unbounded(v) == unb);
            if (!reach[s][v]) {
                assert(bf.dist(v) == std::numeric_limits<long long>::max());
                assert(bf.prev(v) == -1);
                assert(bf.path(v).empty());
            } else if (unb) {
                assert(bf.dist(v) == std::numeric_limits<long long>::lowest());
                assert(bf.path(v).empty());
            } else {
                assert(bf.dist(v) == d[s][v]);
                std::vector<int> p = bf.path(v);
                assert(!p.empty() && p.front() == s && p.back() == v);
                long long total = 0;
                for (int i = 0; i + 1 < int(p.size()); i++) {
                    assert(w[p[i]][p[i + 1]] != inf);
                    total += w[p[i]][p[i + 1]];
                }
                assert(total == d[s][v]);
                assert(bf.prev(v) == (v == s ? -1 : p[p.size() - 2]));
            }
        }
        assert(bf.has_negative_cycle() == any_negative);
    }
    bellman_ford<double> bd(3);
    bd.add_edge(0, 1, 0.5);
    bd.add_edge(1, 2, -1.5);
    bd.solve(0);
    assert(bd.dist(2) == -1.0);
    assert(!bd.has_negative_cycle());
    std::cout << "Hello World\n";
}
Back to top page