Test/AOJ/BellmanFord.test.cpp

• View this file on GitHub
• Last update: 2022-03-14 20:51:37+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B

Depends on

• Bellman-Ford (Graph/BellmanFord.cpp)
• Other/Template.cpp

Code

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

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Graph/BellmanFord.cpp"

int main() {
    int N,M,r;
    cin >> N >> M >> r;
    vector<Edge<long long>> es(M);
    for(int i = 0;i < M;i++) {
        int s,t;
        long long d;
        cin >> s >> t >> d;
        es[i] = {s,t,d};
    }
    vector<long long> dist = bellman_ford(N,M,es,r);
    bool isnegative = false;
    for(int i = 0;i < N;i++) {
        if(dist[i] == -numeric_limits<long long>::max()) isnegative = true;
    }
    if(isnegative) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for(int i = 0;i < N;i++) {
        if(dist[i] == numeric_limits<long long>::max()) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
}

#line 1 "Test/AOJ/BellmanFord.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "Graph/BellmanFord.cpp"
template<typename T>
struct Edge{
    int from,to;
    T cost;
};

template<typename T>
std::vector<T> bellman_ford(const int& node,const int& edge,const std::vector<Edge<T>>& graph,const int& start) {
    std::vector<T> dist(node,std::numeric_limits<T>::max());
    dist[start] = 0;

    for(int i = 0;i < node * 2;i++) {
        for(const auto& [from,to,cost]: graph) {
            if(dist[from] < std::numeric_limits<T>::max() && dist[from] + cost < dist[to])  {
                if(i >= node - 1) dist[to] = std::numeric_limits<T>::max() * static_cast<T>(-1);
                else dist[to] = dist[from] + cost;
            }
        }
    }

    return dist;
}

template<typename T>
bool find_negative_loop(const int& node,const int& edge,const std::vector<Edge<T>>& graph) {
    std::vector<T> dist(node);

    for(int i = 0;i < node;i++) {
        for(const auto& [from,to,cost]: graph) {
            if(dist[to] > dist[from] + cost && i == node - 1) {
                return true;
            }
        }
    }

    return false;
}
#line 8 "Test/AOJ/BellmanFord.test.cpp"

int main() {
    int N,M,r;
    cin >> N >> M >> r;
    vector<Edge<long long>> es(M);
    for(int i = 0;i < M;i++) {
        int s,t;
        long long d;
        cin >> s >> t >> d;
        es[i] = {s,t,d};
    }
    vector<long long> dist = bellman_ford(N,M,es,r);
    bool isnegative = false;
    for(int i = 0;i < N;i++) {
        if(dist[i] == -numeric_limits<long long>::max()) isnegative = true;
    }
    if(isnegative) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for(int i = 0;i < N;i++) {
        if(dist[i] == numeric_limits<long long>::max()) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
}

Back to top page