test/graph/warshallFloyd.aoj_GRL_1_C.test.cpp

• View this file on GitHub
• Last update: 2022-07-12 12:30:29+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

Depends on

• Warshall Floyd (全頂点対最短経路) (graph/warshallFloyd.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"
#include <iostream>
#include <vector>
#include <climits>
#include "graph/warshallFloyd.hpp"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Int long long


int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<Int>> dp(V + 1, vector<Int>(V + 1, LLONG_MAX));
  int s, t, w;
  rep(_, E) {
    cin >> s >> t >> w;
    dp[s][t] = w;
  }
  rep(i, V) { dp[i][i] = 0; }
  warshall_floyd(dp);
  rep(i, V) {
    if (dp[i][i] < 0) {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }
  rep(i, V) {
    rep(j, V) {
      if (dp[i][j] == LLONG_MAX) {
        cout << "INF";
      } else {
        cout << dp[i][j];
      }
      if (j != V - 1) {
        cout << " ";
      } else {
        cout << endl;
      }
    }
  }
}

#line 1 "test/graph/warshallFloyd.aoj_GRL_1_C.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"
#include <iostream>
#include <vector>
#include <climits>
#line 3 "graph/warshallFloyd.hpp"
#include<limits>
using namespace std;

template <typename T>
void warshall_floyd(vector<vector<T>> & dp){
  // dpは隣接行列。dp[i][i] = 0である
  // 結果のdp[i][i]に負が入っていたら負の閉路が存在する。
  T INF = numeric_limits<T>::max();
  for(size_t k=0; k<dp.size(); k++){
    for(size_t i=0; i<dp.size(); i++){
      for(size_t j=0; j<dp.size(); j++){
        if(dp[i][k] == INF || dp[k][j] == INF) continue;
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
      }
    }
  }
}
#line 6 "test/graph/warshallFloyd.aoj_GRL_1_C.test.cpp"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Int long long


int main() {
  int V, E;
  cin >> V >> E;
  vector<vector<Int>> dp(V + 1, vector<Int>(V + 1, LLONG_MAX));
  int s, t, w;
  rep(_, E) {
    cin >> s >> t >> w;
    dp[s][t] = w;
  }
  rep(i, V) { dp[i][i] = 0; }
  warshall_floyd(dp);
  rep(i, V) {
    if (dp[i][i] < 0) {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }
  rep(i, V) {
    rep(j, V) {
      if (dp[i][j] == LLONG_MAX) {
        cout << "INF";
      } else {
        cout << dp[i][j];
      }
      if (j != V - 1) {
        cout << " ";
      } else {
        cout << endl;
      }
    }
  }
}

Back to top page