test/verify/aoj-grl-1b.test.cpp

• View this file on GitHub
• Last update: 2024-09-07 20:55:28+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B
• Link: View error logs on GitHub Actions

Depends on

• Bellmanford(ベルマンフォード法) (graph/bellmanford.hpp)
• graph/graph_template.hpp
• template/template.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B"
#include "template/template.hpp"
#include <vector>

#include "graph/bellmanford.hpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int V,E,r; cin >> V >> E >> r;
  vector<Edge<ll>>edges;
  for (int i=0; i<E; i++) {
    int s,t; ll d;
    cin >> s >> t >> d;
    edges.emplace_back(s,t,d);
  }

  vector<ll> ans = bellman_ford(edges,V,r);
  for (int i=0; i<V; i++) if (ans[i] < -LLINF) {
    cout << "NEGATIVE CYCLE\n";
    return 0;
  }

  for (int i=0; i<V; i++) {
    if (ans[i] >= LLINF) cout << "INF\n";
    else cout << ans[i] << "\n";
  }
  return 0;
}

#line 1 "test/verify/aoj-grl-1b.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B"
#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 3 "test/verify/aoj-grl-1b.test.cpp"
#include <vector>

#line 1 "graph/bellmanford.hpp"



#line 5 "graph/bellmanford.hpp"
#include <queue>
#line 7 "graph/bellmanford.hpp"
#include <limits>

#line 1 "graph/graph_template.hpp"



#line 5 "graph/graph_template.hpp"

template <typename T>
struct Edge {
  int from; int to;
  T cost;

  // default constructor
  Edge () : from(-1), to(-1), cost(T(0)) {}

  Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}

  // unweighted
  Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {}

  bool operator==(const Edge& rhs) const {
    return from == rhs.from && to == rhs.to && cost == rhs.cost;
  }

  bool operator<(const Edge& rhs) const {
    return cost < rhs.cost;
  }
  
  bool operator>(const Edge& rhs) const {
    return cost > rhs.cost;
  }

};


template <typename T>
struct Graph : std::vector<std::vector<Edge<T>>> {

  using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors

  void add_edge(int i, Edge<T> e) {
    (*this)[i].push_back(e);
  }

  void add_edge(Edge<T> e) {
    (*this)[e.from].push_back(e);
  }

  // weighted
  void add_edge(int _from, int _to, T _cost) {
    (*this)[_from].push_back(Edge(_from, _to, _cost));
  }

  // unweighted
  void add_edge(int _from, int _to) {
    (*this)[_from].push_back(Edge(_from, _to, T(1)));
  }

};


#line 10 "graph/bellmanford.hpp"

// 完全にパクリました
// https://ei1333.github.io/library/graph/shortest-path/bellman-ford.hpp
template <typename T> 
std::vector<T> bellman_ford(const std::vector<Edge<T>>& edges, int N, int start) {
  assert(0 <= start && start < N);

  const int M = int(edges.size());
  constexpr T PLINF = std::numeric_limits<T>::max();
  constexpr T MNINF = std::numeric_limits<T>::min();

  std::vector<T> dist(N, PLINF);
  dist[start] = T(0);

  for (int i=0; i<N-1; i++) {
    for (int j=0; j<M; j++) {
      Edge e = edges[j];
      if (dist[e.from] >= PLINF) continue;

      if (dist[e.to] > dist[e.from] + e.cost) {
        dist[e.to] = dist[e.from] + e.cost;
      }
    }
  }

  std::vector<bool> negative(N, false);

  for (int i=0; i<N; i++) {
    for (int j=0; j<M; j++) {
      Edge e = edges[j];

      if (dist[e.from] >= PLINF) continue;
      if (dist[e.to] > dist[e.from] + e.cost) {
        dist[e.to] = dist[e.from] + e.cost;
        negative[e.to] = true;
      }

      if (negative[e.from]) negative[e.to] = true;
    }
  }

  for (int i=0; i<N; i++) if (negative[i]) dist[i] = MNINF;

  return dist;
}


#line 6 "test/verify/aoj-grl-1b.test.cpp"

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int V,E,r; cin >> V >> E >> r;
  vector<Edge<ll>>edges;
  for (int i=0; i<E; i++) {
    int s,t; ll d;
    cin >> s >> t >> d;
    edges.emplace_back(s,t,d);
  }

  vector<ll> ans = bellman_ford(edges,V,r);
  for (int i=0; i<V; i++) if (ans[i] < -LLINF) {
    cout << "NEGATIVE CYCLE\n";
    return 0;
  }

  for (int i=0; i<V; i++) {
    if (ans[i] >= LLINF) cout << "INF\n";
    else cout << ans[i] << "\n";
  }
  return 0;
}

Back to top page