Test/Graph/Normal/WarshallFloyd.test.cpp

View this file on GitHub
Last update: 2025-06-09 16:27:38+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 "./../../../Library/Graph/Normal/WarshallFloyd.hpp"


#include <iostream>


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
template <class T, class S = T>
using P = std::pair<T, S>;

signed main() {
  int n, m;
  cin >> n >> m;
  auto graph = mtd::Graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    graph.addArc(u, v, c);
  }

  auto min_cost = mtd::warshallFloyd(n, graph);

  for (int k = 0; k < n; ++k)
    for (int f = 0; f < n; ++f)
      for (int t = 0; t < n; ++t) {
        if (min_cost[f][t] > min_cost[f][k] + min_cost[k][t]) {
          cout << "NEGATIVE CYCLE" << endl;
          return 0;
        }
      }

  for (const auto r : min_cost) {
    for (auto itr = r.begin(); itr != r.end(); ++itr) {
      if (*itr > 1e17) {
        cout << "INF";
      } else {
        cout << *itr;
      }
      if (itr != std::prev(r.end())) { cout << " "; }
    }
    cout << endl;
  }
}

#line 1 "Test/Graph/Normal/WarshallFloyd.test.cpp"
#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C"

#line 2 "Library/Graph/Normal/WarshallFloyd.hpp"

#include <vector>

#line 2 "Library/Graph/Graph.hpp"
#include <deque>

#include <iostream>

#include <ranges>

#include <tuple>

#line 7 "Library/Graph/Graph.hpp"

namespace mtd {
  template <class Node = long long, class Cost = long long>
  class Graph {
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

  public:
    Graph(int n) : m_n(n), m_graph(n) {}
    Graph(const std::vector<Edges>& edges)
        : m_n(edges.size()), m_graph(edges) {}
    Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v);
        } else {
          addEdge(u, v);
        }
      }
    }
    Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v, c] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v, c);
        } else {
          addEdge(u, v, c);
        }
      }
    }

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
      addArc(f, t, c);
      addArc(t, f, c);
    }
    auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
      m_graph[f].emplace_back(t, c);
    }
    auto getEdges(const Node& from) const {
      class EdgesRange {
        const typename Edges::const_iterator b, e;

      public:
        EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
        auto begin() const { return b; }
        auto end() const { return e; }
      };
      return EdgesRange(m_graph[from]);
    }
    auto getEdges() const {
      std::deque<std::tuple<Node, Node, Cost>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, c] : getEdges(from)) {
          edges.emplace_back(from, to, c);
        }
      }
      return edges;
    }
    auto getEdgesExcludeCost() const {
      std::deque<std::pair<Node, Node>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, _] : getEdges(from)) {
          edges.emplace_back(from, to);
        }
      }
      return edges;
    }
    auto reverse() const {
      auto rev = Graph<Node, Cost>(m_n);
      for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
      return rev;
    }
    auto size() const { return m_n; };
    auto debug(bool directed = false) const {
      for (const auto& [f, t, c] : getEdges()) {
        if (f < t || directed) {
          std::cout << f << " -> " << t << ": " << c << std::endl;
        }
      }
    }
  };
}  // namespace mtd

#line 6 "Library/Graph/Normal/WarshallFloyd.hpp"

namespace mtd {
  template <class Node, class Cost>
  auto warshallFloyd(int n, const Graph<Node, Cost>& graph,
                     const Cost& lim = 1LL << 60) {
    std::vector<std::vector<Cost>> cost(n, std::vector<Cost>(n, lim));
    for (const auto& [from, to, c] : graph.getEdges()) { cost[from][to] = c; }
    for (int i = 0; i < n; ++i) { cost[i][i] = 0; }
    for (int k = 0; k < n; ++k) {
      for (int f = 0; f < n; ++f) {
        for (int t = 0; t < n; ++t) {
          cost[f][t] = std::min(cost[f][t], cost[f][k] + cost[k][t]);
        }
      }
    }
    return cost;
  }
}  // namespace mtd
#line 5 "Test/Graph/Normal/WarshallFloyd.test.cpp"

#line 7 "Test/Graph/Normal/WarshallFloyd.test.cpp"

using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
template <class T, class S = T>
using P = std::pair<T, S>;

signed main() {
  int n, m;
  cin >> n >> m;
  auto graph = mtd::Graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    graph.addArc(u, v, c);
  }

  auto min_cost = mtd::warshallFloyd(n, graph);

  for (int k = 0; k < n; ++k)
    for (int f = 0; f < n; ++f)
      for (int t = 0; t < n; ++t) {
        if (min_cost[f][t] > min_cost[f][k] + min_cost[k][t]) {
          cout << "NEGATIVE CYCLE" << endl;
          return 0;
        }
      }

  for (const auto r : min_cost) {
    for (auto itr = r.begin(); itr != r.end(); ++itr) {
      if (*itr > 1e17) {
        cout << "INF";
      } else {
        cout << *itr;
      }
      if (itr != std::prev(r.end())) { cout << " "; }
    }
    cout << endl;
  }
}