competitive-programing

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

View the Project on GitHub Astral-23/competitive-programing

:heavy_check_mark: verify/bellman_ford.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp"
#include "../Utility/template.hpp"
#include "../Utility/modint.hpp"
#include "../Graph/min_distance.hpp"


int main() {
    
    
    int n, m, r;
    cin >> n >> m >> r;
    vec<vec<pair<long long, long long>>> g(n);
    rep(i, 0, m) {
        ll s, t, d;
        cin >> s >> t >> d;
        g[s].push_back({d, t});
    }
    min_distance<modint998244353> G(n, g);
    if(G.run_bellman_ford(r)) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    else {
        for(ll x : G.distance()) {
            if(x == LLONG_MAX / 4) cout << "INF" << endl;
else             cout << x << endl;
        }
    }
}
#line 1 "verify/bellman_ford.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Utility/modint.hpp"

// 動的mod : template<int mod> を消して、上の方で変数modを宣言
template <uint32_t mod> struct modint {
    using mm = modint;
    uint32_t x;
    modint() : x(0) {}
    TT modint(T a = 0) : x((ll(a) % mod + mod)) {
        if (x >= mod) x -= mod;
    }

    friend mm operator+(mm a, mm b) {
        a.x += b.x;
        if (a.x >= mod) a.x -= mod;
        return a;
    }
    friend mm operator-(mm a, mm b) {
        a.x -= b.x;
        if (a.x >= mod) a.x += mod;
        return a;
    }

    mm operator-() const { return mod - x; }

    //+と-だけで十分な場合、以下は省略して良いです。

    friend mm operator*(mm a, mm b) { return (uint64_t)(a.x) * b.x; }
    friend mm operator/(mm a, mm b) { return a * b.inv(); }
    friend mm &operator+=(mm &a, mm b) { return a = a + b; }
    friend mm &operator-=(mm &a, mm b) { return a = a - b; }
    friend mm &operator*=(mm &a, mm b) { return a = a * b; }
    friend mm &operator/=(mm &a, mm b) { return a = a * b.inv(); }

    mm inv() const {
        assert(x != 0);
        return pow(mod - 2);
    }
    mm pow(ll y) const {
        mm res = 1;
        mm v = *this;
        while (y) {
            if (y & 1) res *= v;
            v *= v;
            y /= 2;
        }
        return res;
    }

    friend istream &operator>>(istream &is, mm &a) {
        ll t;
        cin >> t;
        a = mm(t);
        return is;
    }

    friend ostream &operator<<(ostream &os, mm a) { return os << a.x; }

    bool operator==(mm a) { return x == a.x; }
    bool operator!=(mm a) { return x != a.x; }

    bool operator<(const mm &a) const { return x < a.x; }
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1'000'000'007>;
/*
@brief modint
*/
#line 1 "Graph/min_distance.hpp"

template <typename T> struct min_distance {
    using pll = pair<ll, ll>;

  private:
    int n, s;
    vec<vec<pll>> g;
    vec<ll> dist;
    vec<T> cnt;
    vec<int> pre;
    int built;
    ll inf = LLONG_MAX / 4;

    void init() {
        fill(all(dist), inf);
        fill(all(cnt), 0);
        fill(all(pre), -1);
    }

  public:
    min_distance(int n) : n(n), dist(n), cnt(n), pre(n), built(0) {};
    min_distance(int n, vec<vec<pll>> &g)
        : n(n), g(g), dist(n), cnt(n), pre(n), built(0) {}

    void add_edge(int from, int to, ll cost) { g[from].emplace_back(cost, to); }

    void run_dijkstra(int S) {
        built = 1;
        init();
        s = S;
        dist[s] = 0;
        cnt[s] = 1;
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>,
                       greater<pair<ll, ll>>>
            que;
        que.push({dist[s], s});
        while (que.empty() == false) {
            auto [c, v] = que.top();
            que.pop();
            if (dist[v] < c) continue;
            for (auto [cost, to] : g[v]) {
                if (chmin(dist[to], cost + c)) {
                    cnt[to] = cnt[v];
                    pre[to] = v;
                    que.push({dist[to], to});

                } else if (dist[to] == cost + c) {
                    cnt[to] += cnt[v];
                }
            }
        }
    }

    bool run_bellman_ford(int S) {
        built = 2;
        init();
        s = S;
        dist[s] = 0;
        cnt[s] = 1;
        int last = -1;
        rep(i, 0, n) {
            bool found = false;
            rep(v, 0, n) if (dist[v] != inf) {
                for (auto [cost, to] : g[v]) {
                    if (chmin(dist[to], dist[v] + cost)) {
                        found = true;
                        pre[to] = v;
                    }
                }
            }
            if (found) last = i;
        }

        if (last == n - 1) return true;
        return false;
    }

    vec<vec<ll>> run_warshall_floyd() {
        vec<vec<ll>> d(n, vec<ll>(n, inf));
        rep(i, 0, n) d[i][i] = 0;
        rep(i, 0, n) for (auto [cost, to] : g[i]) {
            chmin(d[i][to], cost);
            chmin(d[to][i], cost);
        }

        rep(k, 0, n) rep(i, 0, n) rep(j, 0, n) {
            chmin(d[i][j], d[i][k] + d[k][j]);
        }
        return d;
    }

    vec<ll> distance() {
        assert(built != 0);
        return dist;
    }

    vec<T> count_path() {
        assert(built == 1);
        return cnt;
    }

    vec<int> path(int t) {
        assert(built != 0);
        vec<int> res;
        while (1) {
            res.push_back(t);
            if (t == s) break;
            t = pre[t];
        }
        reverse(all(res));
        return res;
    }
};
/*
@brief 最短経路
@docs doc/min_distance.md
*/
#line 5 "verify/bellman_ford.test.cpp"


int main() {
    
    
    int n, m, r;
    cin >> n >> m >> r;
    vec<vec<pair<long long, long long>>> g(n);
    rep(i, 0, m) {
        ll s, t, d;
        cin >> s >> t >> d;
        g[s].push_back({d, t});
    }
    min_distance<modint998244353> G(n, g);
    if(G.run_bellman_ford(r)) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    else {
        for(ll x : G.distance()) {
            if(x == LLONG_MAX / 4) cout << "INF" << endl;
else             cout << x << endl;
        }
    }
}
Back to top page