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

• View this file on GitHub
• Last update: 2021-05-27 02:04:57+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

Depends on

• graph/bellman_ford.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"
#include <iostream>
#include <vector>
#include "../graph/bellman_ford.hpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int V, E, r; 
  std::cin >> V >> E >> r;
  std::vector<std::vector<std::pair<int, long long>>> g(V);
  for(int i=0; i<E; i++) {
    int s, t, d; std::cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  auto p = bellman_ford<long long>(g, r);
  
  if(p.second) std::cout << "NEGATIVE CYCLE" << '\n';
  else{
    for(int i=0; i<V; i++) {
      if(p.first[i] == (1LL<<60)) std::cout << "INF" << '\n';
      else std::cout << p.first[i] << '\n';
    }
  }
  
  return 0;
}

#line 1 "test/aoj-grl-1-b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B"
#include <iostream>
#include <vector>
#line 1 "graph/bellman_ford.hpp"
#include<queue>
#line 3 "graph/bellman_ford.hpp"
template<typename T>
std::pair<std::vector<T>, bool> bellman_ford(std::vector<std::vector<std::pair<int, T>>> &g, int s, int t=-1) {
  int n = g.size();
  std::vector<T> dist(n, (1LL<<60));
  dist[s] = 0;
  bool update = true;
  for(int i=0; i<n; i++) {
    update = false;
    for(int v=0; v<n; v++) {
      for(auto[u, c] : g[v]){
        if(dist[v] != (1LL<<60) && dist[u] > dist[v] + c){
          dist[u] = dist[v] + c;
          update = true;
        }
      }
    }
    if(!update) return {dist, false};
  }
  if(t == -1) return {dist, true};
  std::vector<bool> negative(n, false); 
  for(int i=0; i<n; ++i){
    for(int v=0; v<n; v++) {
      for(auto[u, c] : g[v]){
        if(dist[v] != (1LL<<60) && dist[u] > dist[v] + c){
          dist[u] = dist[v] + c;
          negative[u] = true;
        }
        if(negative[v]) negative[u] = true;
      }
    }
  }
  return {dist, negative[t]};
}
#line 5 "test/aoj-grl-1-b.test.cpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int V, E, r; 
  std::cin >> V >> E >> r;
  std::vector<std::vector<std::pair<int, long long>>> g(V);
  for(int i=0; i<E; i++) {
    int s, t, d; std::cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  auto p = bellman_ford<long long>(g, r);
  
  if(p.second) std::cout << "NEGATIVE CYCLE" << '\n';
  else{
    for(int i=0; i<V; i++) {
      if(p.first[i] == (1LL<<60)) std::cout << "INF" << '\n';
      else std::cout << p.first[i] << '\n';
    }
  }
  
  return 0;
}

Back to top page