test/aoj/grl_1_b.test.cpp

View this file on GitHub
Last update: 2022-12-30 13:43:35+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B

Depends on

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/graph/bellman_ford.hpp"
#include "../../src/graph/template.hpp"

int main() {
  int V, E, r;
  cin >> V >> E >> r;
  BellmanFord<int> bellman_ford(V, r);
  Edges<long long> edges;
  for (int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    bellman_ford.add_edge(s, t, d);
  }
  bellman_ford.build();
  if (bellman_ford.has_negative_cycle()) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    for (int i = 0; i < V; ++i) {
      if (bellman_ford.is_unreachable(i)) {
        cout << "INF" << endl;
      } else {
        cout << bellman_ford.shortest_path_value(i) << endl;
      }
    }
  }
  return 0;
}

#line 1 "test/aoj/grl_1_b.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/graph/bellman_ford.hpp"

#line 4 "src/graph/bellman_ford.hpp"
using namespace std;

#line 2 "src/graph/template.hpp"

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

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

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 7 "src/graph/bellman_ford.hpp"

template <typename T> struct BellmanFord {
private:
  int n;
  int start;
  Edges<T> edges;
  vector<T> dist;
  bool _has_negative_cycle = false;
  T MAX = numeric_limits<T>::max();

public:
  BellmanFord(int n, int start) : n(n), start(start) {
    dist.resize(n, MAX);
    dist[start] = 0;
  }

  void add_edge(int start, int to, long long cost) {
    edges.emplace_back(start, to, cost);
  }

  void build() {
    for (int i = 0; i < n - 1; ++i) {
      for (auto &edge : edges) {
        if (dist[edge.from] == MAX) {
          continue;
        }
        dist[edge.to] = min(dist[edge.to], dist[edge.from] + edge.cost);
      }
    }
    for (auto &edge : edges) {
      if (dist[edge.from] == MAX) {
        continue;
      }
      if (dist[edge.to] > dist[edge.from] + edge.cost) {
        _has_negative_cycle = true;
        break;
      }
    }
  }

  T shortest_path_value(int t) { return dist[t]; }

  bool is_unreachable(int t) { return dist[t] == MAX; }

  bool has_negative_cycle() { return _has_negative_cycle; }
};
#line 9 "test/aoj/grl_1_b.test.cpp"

int main() {
  int V, E, r;
  cin >> V >> E >> r;
  BellmanFord<int> bellman_ford(V, r);
  Edges<long long> edges;
  for (int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    bellman_ford.add_edge(s, t, d);
  }
  bellman_ford.build();
  if (bellman_ford.has_negative_cycle()) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    for (int i = 0; i < V; ++i) {
      if (bellman_ford.is_unreachable(i)) {
        cout << "INF" << endl;
      } else {
        cout << bellman_ford.shortest_path_value(i) << endl;
      }
    }
  }
  return 0;
}