verify/AizuOnlineJudge/graph/shortest-path/GRL_1_C.test.cpp

• View this file on GitHub
• Last update: 2024-06-26 17:11:19+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C

Depends on

• Warshall Floyd (graph/shortest-path/WarshallFloyd.hpp)

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 "../../../../graph/shortest-path/WarshallFloyd.hpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int v, e;
  long long inf = numeric_limits<long long>::max();
  cin >> v >> e;
  vector<vector<pair<int, int>>> g(v);
  for (int i = 0; i < e; i++) {
    int s, t, d;
    cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  vector<vector<long long>> res = warshallFloyd<long long>(g);
  for (int i = 0; i < v; i++) {
    if (res[i][i] < 0) {
      cout << "NEGATIVE CYCLE" << "\n";
      return 0;
    }
  }
  for (int i = 0; i < v; i++) {
    for (int j = 0; j < v; j++) {
      if (res[i][j] == inf) {
        cout << "INF";
      } else {
        cout << res[i][j];
      }
      if (j == v - 1) {
        cout << "\n";
      } else {
        cout << " ";
      }
    }
  }
}

#line 1 "verify/AizuOnlineJudge/graph/shortest-path/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 "graph/shortest-path/WarshallFloyd.hpp"
template <class T>
vector<vector<T>> warshallFloyd(vector<vector<pair<int, int>>> &g) {
  int n = g.size();
  T inf = numeric_limits<T>::max();
  vector<vector<T>> a(n, vector<T>(n, inf));
  for (int i = 0; i < n; i++) {
    a[i][i] = 0;
    for (auto p : g[i]) {
      a[i][p.first] = p.second;
    }
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (a[i][k] == inf or a[k][j] == inf) continue;
        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
      }
    }
  }
  return a;
}

template <class T>
vector<vector<T>> warshallFloyd(vector<vector<int>> g) {
  int n = g.size();
  T inf = numeric_limits<T>::max();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (g[i][j] < 0) g[i][j] = inf;
    }
  }
  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 or g[k][j] == inf) continue;
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  return g;
}
#line 5 "verify/AizuOnlineJudge/graph/shortest-path/GRL_1_C.test.cpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int v, e;
  long long inf = numeric_limits<long long>::max();
  cin >> v >> e;
  vector<vector<pair<int, int>>> g(v);
  for (int i = 0; i < e; i++) {
    int s, t, d;
    cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  vector<vector<long long>> res = warshallFloyd<long long>(g);
  for (int i = 0; i < v; i++) {
    if (res[i][i] < 0) {
      cout << "NEGATIVE CYCLE" << "\n";
      return 0;
    }
  }
  for (int i = 0; i < v; i++) {
    for (int j = 0; j < v; j++) {
      if (res[i][j] == inf) {
        cout << "INF";
      } else {
        cout << res[i][j];
      }
      if (j == v - 1) {
        cout << "\n";
      } else {
        cout << " ";
      }
    }
  }
}

Back to top page