test/aoj/grl/grl_1_b.test.cpp

View this file on GitHub
Last update: 2024-05-04 18:06:16+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

Depends on

Bellman-Ford Algorithm (ベルマン-フォード法) (lib/graph/bellman_ford.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/bellman_ford.hpp"

int n, m, r;
vector<array<long long, 3>> E;

int main(){
    cin >> n >> m >> r;
    E = vector<array<long long, 3>>();

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        // a -> b : cost c
        E.push_back({a, b, c});
    }
    
    vector<long long> ans = bellman_ford(E, n, r);
    bool is_ncycle = false;
    for(int i = 0; i < n; i++){
        if(ans[i] <= -0x1fffffffffffffff){
            is_ncycle = true;
        }
    }
    if(is_ncycle){
        cout << "NEGATIVE CYCLE" << "\n";
    }else{
        for(int i = 0; i < n; i++){
            if(ans[i] >= 0x1fffffffffffffff){
                cout << "INF" << "\n";
            }else{
                cout << ans[i] << "\n";
            }
        }
    }
}

#line 1 "test/aoj/grl/grl_1_b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/bellman_ford.hpp"

/**
 * @brief Bellman-Ford Algorithm (ベルマン-フォード法)
 * @docs docs/graph/bellman_ford.md
 */

template <typename T>
vector<long long> bellman_ford(const vector<T> &E, const int &n, const int &x){
    const long long INF = 0x1fffffffffffffff;
    vector<long long> cost(n, INF);
    cost[x] = 0;
    for(int i = 0; i < n - 1; i++){
        for(auto [from, to, t] : E){
            if(cost[from] == INF) continue;
            cost[to] = min(cost[to], cost[from] + t);
        }
    }
    for(int i = 0; i < n - 1; i++){
        for(auto [from, to, t] : E){
            if(cost[from] == INF) continue;
            if(cost[from] + t < cost[to]){
                cost[to] = -INF;
            }
        }
    }
    return cost;
}
#line 6 "test/aoj/grl/grl_1_b.test.cpp"

int n, m, r;
vector<array<long long, 3>> E;

int main(){
    cin >> n >> m >> r;
    E = vector<array<long long, 3>>();

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        // a -> b : cost c
        E.push_back({a, b, c});
    }
    
    vector<long long> ans = bellman_ford(E, n, r);
    bool is_ncycle = false;
    for(int i = 0; i < n; i++){
        if(ans[i] <= -0x1fffffffffffffff){
            is_ncycle = true;
        }
    }
    if(is_ncycle){
        cout << "NEGATIVE CYCLE" << "\n";
    }else{
        for(int i = 0; i < n; i++){
            if(ans[i] >= 0x1fffffffffffffff){
                cout << "INF" << "\n";
            }else{
                cout << ans[i] << "\n";
            }
        }
    }
}