test/aoj/GRL_1_C.test.cpp

View this file on GitHub
Last update: 2021-08-01 23:46:19+09: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 "../../graph/warshall-floyd.hpp"

#include <iostream>
using namespace std;

typedef long long ll;

int main() {
  int V, E;
  cin >> V >> E;
  Graph<ll> g(V);
  for (int i = 0; i < E; ++i) {
    int x, y; ll d;
    cin >> x >> y >> d;
    g[x].emplace_back(x, y, d);
  }
  WarshallFloyd<ll> wf(g);
  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 (j > 0) cout << " ";
      if (wf.dist[i][j] == wf.INF) cout << "INF";
      else cout << wf.dist[i][j];
    }
    cout << endl;
  }
}

#line 1 "test/aoj/GRL_1_C.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"
#line 1 "graph/warshall-floyd.hpp"


// @title warshall-floyd
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

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

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 5 "graph/warshall-floyd.hpp"

#include <limits>
#line 8 "graph/warshall-floyd.hpp"

template < typename T >
struct WarshallFloyd {
  const T INF; // dijkstraとINFの値を揃えるため、型Tの最大値の半分を使う
  const int V; // 頂点数
  Graph<T> g;
  std::vector<std::vector<T>> dist;
  WarshallFloyd(Graph<T> &g): INF(std::numeric_limits<T>::max()/2), V(g.size()), g(g), dist(V, std::vector<T>(V, INF)) { init(); }
  WarshallFloyd(Graph<T> &g, int V): INF(std::numeric_limits<T>::max()/2), V(V), g(g), dist(V, std::vector<T>(V, INF)) { init(); }
  void init() {
    for (int i = 0; i < V; ++i) {
      dist[i][i] = 0;
      for (auto &e: g[i]) dist[i][e.to] = e.cost;
    }
    for (int k = 0; k < V; ++k) {
      for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
          if (dist[i][k] == INF || dist[k][j] == INF) continue;
          T d = dist[i][k]+dist[k][j];
          if (dist[i][j] > d) dist[i][j] = d;
        }
      }
    }
  }
  bool has_negative_cycle() {
    for (int i = 0; i < V; ++i) {
      if (dist[i][i] < 0) return true;
    }
    return false;
  }
};


#line 3 "test/aoj/GRL_1_C.test.cpp"

#line 5 "test/aoj/GRL_1_C.test.cpp"
using namespace std;

typedef long long ll;

int main() {
  int V, E;
  cin >> V >> E;
  Graph<ll> g(V);
  for (int i = 0; i < E; ++i) {
    int x, y; ll d;
    cin >> x >> y >> d;
    g[x].emplace_back(x, y, d);
  }
  WarshallFloyd<ll> wf(g);
  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 (j > 0) cout << " ";
      if (wf.dist[i][j] == wf.INF) cout << "INF";
      else cout << wf.dist[i][j];
    }
    cout << endl;
  }
}