test/aoj-grl-1-c.test.cpp

• View this file on GitHub
• Last update: 2021-05-27 02:04:57+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C

Depends on

• graph/warshall_floyd.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"
#include <iostream>
#include <vector>
#include "../graph/warshall_floyd.hpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int V, E; 
  std::cin >> V >> E;
  std::vector<std::vector<std::pair<int, long long>>> g(V);
  for(int i=0; i<E; i++) {
    int s, t, d; std::cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  auto d = warshall_floyd<long long>(g);
  for(int i=0; i<V; i++) {
    if(d[i][i] < 0) {
      std::cout << "NEGATIVE CYCLE" << '\n';
      return 0;
    }
  }
  for(int i=0; i<V; i++) {
    for(int j=0; j<V; j++) {
      if(j != 0) std::cout << ' ';
      if(d[i][j] >= 1e10) std::cout << "INF";
      else std::cout << d[i][j];
    }
    std::cout << '\n';
  }
  
  return 0;
}

#line 1 "test/aoj-grl-1-c.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C"
#include <iostream>
#include <vector>
#line 2 "graph/warshall_floyd.hpp"
template<typename T = long>
std::vector<std::vector<T>> warshall_floyd(std::vector<std::vector<std::pair<int, T>>> &g) {
  int n = g.size();
  std::vector<std::vector<T>> dist(n, std::vector<T>(n,(1LL<<60)));
  for(int v=0; v<n; v++) {
    dist[v][v] = 0;
    for(auto[u, c]: g[v]) {
      dist[v][u] = std::min(dist[v][u], c);
    }
  }
  for(int k=0; k<n; k++) {
    for(int i=0; i<n; i++) {
      for(int j=0; j<n; j++) {
        dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  return dist;
}
#line 5 "test/aoj-grl-1-c.test.cpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int V, E; 
  std::cin >> V >> E;
  std::vector<std::vector<std::pair<int, long long>>> g(V);
  for(int i=0; i<E; i++) {
    int s, t, d; std::cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  auto d = warshall_floyd<long long>(g);
  for(int i=0; i<V; i++) {
    if(d[i][i] < 0) {
      std::cout << "NEGATIVE CYCLE" << '\n';
      return 0;
    }
  }
  for(int i=0; i<V; i++) {
    for(int j=0; j<V; j++) {
      if(j != 0) std::cout << ' ';
      if(d[i][j] >= 1e10) std::cout << "INF";
      else std::cout << d[i][j];
    }
    std::cout << '\n';
  }
  
  return 0;
}

Back to top page