Test/AOJ/WarshallFloyd.test.cpp

• View this file on GitHub
• Last update: 2021-06-18 21:34:36+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C

Depends on

• Warshall-Floyd (Graph/WarshallFloyd.cpp)
• Other/Template.cpp

Code

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

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

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

int main() {
    int N,M;
    cin >> N >> M;
    vector<vector<long long>> dist(N,vector<long long>(N,INF));
    for(int i = 0;i < N;i++) dist[i][i] = 0;
    for(int i = 0;i < M;i++) {
        int s,t;
        long long d;
        cin >> s >> t >> d;
        dist[s][t] = d;
    }
    dist = WarshallFloyd(N,dist);
    bool isnegative = false;
    for(int i = 0;i < N;i++) {
        if(dist[i][i] < 0) isnegative = true;
    }
    if(isnegative) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            if(dist[i][j] == INF) cout << "INF";
            else cout << dist[i][j];
            if(j != N - 1) cout << " ";
        }
        cout << endl;
    }
}

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

#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/WarshallFloyd.cpp"
vector<vector<long long>> WarshallFloyd(const int& N,const vector<vector<long long>> dist) {
    vector<vector<long long>> ret = dist;
    for(int k = 0;k < N;k++) {
        for(int i = 0;i < N;i++) {
            for(int j = 0;j < N;j++) {
                if(ret[i][k] != INF && ret[k][j] != INF) {
                    chmin(ret[i][j],ret[i][k] + ret[k][j]);
                }
            }
        }
    }
    return ret;
}
#line 8 "Test/AOJ/WarshallFloyd.test.cpp"

int main() {
    int N,M;
    cin >> N >> M;
    vector<vector<long long>> dist(N,vector<long long>(N,INF));
    for(int i = 0;i < N;i++) dist[i][i] = 0;
    for(int i = 0;i < M;i++) {
        int s,t;
        long long d;
        cin >> s >> t >> d;
        dist[s][t] = d;
    }
    dist = WarshallFloyd(N,dist);
    bool isnegative = false;
    for(int i = 0;i < N;i++) {
        if(dist[i][i] < 0) isnegative = true;
    }
    if(isnegative) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < N;j++) {
            if(dist[i][j] == INF) cout << "INF";
            else cout << dist[i][j];
            if(j != N - 1) cout << " ";
        }
        cout << endl;
    }
}

Back to top page