tests/aoj/floyd_warshall.all_pairs_shortest_path.test.cpp

View this file on GitHub
Last update: 2020-10-29 16:39:06+01:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"

#include "../../code/graphs/floydWarshall.cc"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int V, E;
  cin >> V >> E;

  adj.assign(V, vector<ll>(V, INF));

  F0R(i, E) {
      int u, v, d;
      cin >> u >> v >> d;
      ckmin(adj[u][v], (ll)d);
  }

  F0R(i, V) adj[i][i] = 0;
  floydWarshall();

  if(negCycle) {
      cout << "NEGATIVE CYCLE\n";
  } else {
      F0R(i, V) {
        F0R(j, V) {
          if(j) cout << ' ';
          if(adj[i][j] == INF)
            cout << "INF";
          else
            cout << adj[i][j];
        }
        cout << endl;
      }
  }
}

#line 1 "tests/aoj/floyd_warshall.all_pairs_shortest_path.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/floydWarshall.cc"
const ll INF = 1e18;
vector<vector<ll>> adj;  // adjacency matrix
bool negCycle = false;
void floydWarshall() {
  F0R (k, SZ(adj)) F0R (i, SZ(adj)) F0R (j, SZ(adj))
    if(adj[i][k] != INF && adj[k][j] != INF)
      ckmin(adj[i][j], adj[i][k] + adj[k][j]);
  F0R (k, SZ(adj)) if(adj[k][k] < 0) negCycle = true;
}
#line 4 "tests/aoj/floyd_warshall.all_pairs_shortest_path.test.cpp"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int V, E;
  cin >> V >> E;

  adj.assign(V, vector<ll>(V, INF));

  F0R(i, E) {
      int u, v, d;
      cin >> u >> v >> d;
      ckmin(adj[u][v], (ll)d);
  }

  F0R(i, V) adj[i][i] = 0;
  floydWarshall();

  if(negCycle) {
      cout << "NEGATIVE CYCLE\n";
  } else {
      F0R(i, V) {
        F0R(j, V) {
          if(j) cout << ' ';
          if(adj[i][j] == INF)
            cout << "INF";
          else
            cout << adj[i][j];
        }
        cout << endl;
      }
  }
}