test/aoj/grl_1_c.test.cpp

View this file on GitHub
Last update: 2022-12-19 02:10:28+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C

Depends on

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 "../../src/graph/template.hpp"
#include "../../src/graph/warshall_floyd.hpp"

int main() {
  int V, E;
  cin >> V >> E;
  WarshallFloyd<long long> wf(V);
  for (int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    wf.add_edge(s, t, d);
  }
  wf.build();
  if (wf.has_negative_cycle()) {
    cout << "NEGATIVE CYCLE" << endl;
    return 0;
  }
  for (int i = 0; i < V; ++i) {
    for (int j = 0; j < V; ++j) {
      if (wf.is_unreachable(i, j)) {
        cout << "INF";
      } else {
        cout << wf.shortest_path_value(i, j);
      }

      if (j == V - 1) {
        cout << endl;
      } else {
        cout << " ";
      }
    }
  }
  return 0;
}

#line 1 "test/aoj/grl_1_c.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 2 "src/graph/template.hpp"

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 2 "src/graph/warshall_floyd.hpp"

#line 4 "src/graph/warshall_floyd.hpp"
using namespace std;

#line 7 "src/graph/warshall_floyd.hpp"

template <typename T> struct WarshallFloyd {
private:
  const T INF = numeric_limits<T>::max();
  int n;
  Matrix<T> g;

public:
  WarshallFloyd(int n) : n(n), g(n, vector<T>(n, INF)) {
    for (int i = 0; i < n; ++i) {
      g[i][i] = 0;
    }
  }

  void add_edge(int u, int v, T c) { g[u][v] = c; }

  void build() {
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (g[i][k] == INF || g[k][j] == INF) {
            continue;
          }
          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }
  }

  bool has_negative_cycle() {
    for (int i = 0; i < n; ++i) {
      if (g[i][i] < 0) {
        return true;
      }
    }
    return false;
  }

  T shortest_path_value(int s, int t) { return g[s][t]; }

  bool is_unreachable(int s, int t) { return g[s][t] == INF; }
};
#line 9 "test/aoj/grl_1_c.test.cpp"

int main() {
  int V, E;
  cin >> V >> E;
  WarshallFloyd<long long> wf(V);
  for (int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    wf.add_edge(s, t, d);
  }
  wf.build();
  if (wf.has_negative_cycle()) {
    cout << "NEGATIVE CYCLE" << endl;
    return 0;
  }
  for (int i = 0; i < V; ++i) {
    for (int j = 0; j < V; ++j) {
      if (wf.is_unreachable(i, j)) {
        cout << "INF";
      } else {
        cout << wf.shortest_path_value(i, j);
      }

      if (j == V - 1) {
        cout << endl;
      } else {
        cout << " ";
      }
    }
  }
  return 0;
}