グラフ/最短路問題/Bellman–Ford 法
(test/graph/shortest_path/bellman-ford.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• Bellman–Ford 法 (include/emthrm/graph/shortest_path/bellman-ford.hpp)

Code

/*
 * @title グラフ/最短路問題/Bellman–Ford 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/shortest_path/bellman-ford.hpp"

int main() {
  int v, e, r;
  std::cin >> v >> e >> r;
  std::vector<std::vector<emthrm::Edge<long long>>> graph(v);
  while (e--) {
    int s, t, d;
    std::cin >> s >> t >> d;
    graph[s].emplace_back(s, t, d);
  }
  emthrm::BellmanFord<long long> bellman_ford(graph);
  if (bellman_ford.has_negative_cycle(r)) {
    std::cout << "NEGATIVE CYCLE\n";
    return 0;
  }
  for (int i = 0; i < v; ++i) {
    if (bellman_ford.dist[i] == bellman_ford.inf) {
      std::cout << "INF\n";
    } else {
      std::cout << bellman_ford.dist[i] << '\n';
    }
  }
  return 0;
}

#line 1 "test/graph/shortest_path/bellman-ford.test.cpp"
/*
 * @title グラフ/最短路問題/Bellman–Ford 法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/shortest_path/bellman-ford.hpp"



#include <algorithm>
#include <cassert>
#include <limits>
#line 8 "include/emthrm/graph/shortest_path/bellman-ford.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/shortest_path/bellman-ford.hpp"

namespace emthrm {

template <typename CostType>
struct BellmanFord {
  const CostType inf;
  std::vector<CostType> dist;

  BellmanFord(const std::vector<std::vector<Edge<CostType>>>& graph,
              const CostType inf = std::numeric_limits<CostType>::max())
      : inf(inf), is_built(false), graph(graph) {}

  bool has_negative_cycle(const int s) {
    is_built = true;
    const int n = graph.size();
    dist.assign(n, inf);
    dist[s] = 0;
    prev.assign(n, -1);
    for (int step = 0; step < n; ++step) {
      bool is_updated = false;
      for (int i = 0; i < n; ++i) {
        if (dist[i] == inf) continue;
        for (const Edge<CostType>& e : graph[i]) {
          if (dist[e.dst] > dist[i] + e.cost) {
            dist[e.dst] = dist[i] + e.cost;
            prev[e.dst] = i;
            is_updated = true;
          }
        }
      }
      if (!is_updated) return false;
    }
    return true;
  }

  std::vector<int> build_path(int t) const {
    assert(is_built);
    std::vector<int> res;
    for (; t != -1; t = prev[t]) {
      res.emplace_back(t);
    }
    std::reverse(res.begin(), res.end());
    return res;
  }

 private:
  bool is_built;
  std::vector<int> prev;
  std::vector<std::vector<Edge<CostType>>> graph;
};

}  // namespace emthrm


#line 12 "test/graph/shortest_path/bellman-ford.test.cpp"

int main() {
  int v, e, r;
  std::cin >> v >> e >> r;
  std::vector<std::vector<emthrm::Edge<long long>>> graph(v);
  while (e--) {
    int s, t, d;
    std::cin >> s >> t >> d;
    graph[s].emplace_back(s, t, d);
  }
  emthrm::BellmanFord<long long> bellman_ford(graph);
  if (bellman_ford.has_negative_cycle(r)) {
    std::cout << "NEGATIVE CYCLE\n";
    return 0;
  }
  for (int i = 0; i < v; ++i) {
    if (bellman_ford.dist[i] == bellman_ford.inf) {
      std::cout << "INF\n";
    } else {
      std::cout << bellman_ford.dist[i] << '\n';
    }
  }
  return 0;
}

Back to top page