test/aoj/grl/grl_1_c.test.cpp

• View this file on GitHub
• Last update: 2025-01-09 22:05:35+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

Depends on

• Floyd-Warshall Algorithm (ワーシャルフロイド法) (lib/graph/warshall_floyd.hpp)

Code

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

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

const long long INF = 0x1fffffffffffffff;

int main(){
    int n, m; cin >> n >> m;
    vector<vector<long long>> d(n, vector<long long>(n, INF));

    for(int i = 0; i < n; i++){
        d[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = c;
    }

    warshall_floyd(d, INF);
    for(int i = 0; i < n; i++){
        if(d[i][i] < 0){
            cout << "NEGATIVE CYCLE" << "\n";
            return 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(j >= 1) cout << " ";
            if(d[i][j] == INF){
                cout << "INF";
            }else{
                cout << d[i][j];
            }
        }
        cout << "\n";
    }
}

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

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

/**
 * @brief Floyd-Warshall Algorithm (ワーシャルフロイド法)
 * @docs docs/graph/warshall_floyd.md
 */

template <typename T>
void warshall_floyd(vector<vector<T>> &d, const T &INF) {
    int n = d.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(d[j][i] == INF || d[i][k] == INF) continue;
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
}

template <typename T>
void warshall_floyd_add(vector<vector<T>> &d, int u, int v, T cost) {
    int n = d.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            d[i][j] = min(d[i][j], d[i][u] + cost + d[v][j]);
        }
    }
}
#line 6 "test/aoj/grl/grl_1_c.test.cpp"

const long long INF = 0x1fffffffffffffff;

int main(){
    int n, m; cin >> n >> m;
    vector<vector<long long>> d(n, vector<long long>(n, INF));

    for(int i = 0; i < n; i++){
        d[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = c;
    }

    warshall_floyd(d, INF);
    for(int i = 0; i < n; i++){
        if(d[i][i] < 0){
            cout << "NEGATIVE CYCLE" << "\n";
            return 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(j >= 1) cout << " ";
            if(d[i][j] == INF){
                cout << "INF";
            }else{
                cout << d[i][j];
            }
        }
        cout << "\n";
    }
}

Back to top page