test/aoj/GRL_1_B.test.cpp

View this file on GitHub
Last update: 2020-10-27 16:01:15+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

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

#define call_from_test
#include "../../tools/drop.cpp"
#include "../../graph/bellmanford.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m,r;
  cin>>n>>m>>r;

  BellmanFord<int> G(n);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    G.add_edge(a,b,c);
  }

  int neg_loop;
  auto res=G.build(r,neg_loop);
  if(neg_loop) drop("NEGATIVE CYCLE");

  for(int x:res){
    if(x==numeric_limits<int>::max()) cout<<"INF\n";
    else cout<<x<<"\n";
  }
  cout<<flush;
  return 0;
}

#line 1 "test/aoj/GRL_1_B.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

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

#define call_from_test
#line 1 "tools/drop.cpp"

#line 3 "tools/drop.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "graph/bellmanford.cpp"

#line 3 "graph/bellmanford.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct BellmanFord{
  struct edge{
    int u,v;
    T w;
    edge(int u,int v,T w):u(u),v(v),w(w){}
  };

  vector< vector<int> > G;
  vector<int> used,reach;
  BellmanFord(int n):G(n),used(n,0),reach(n,1){}

  vector<edge> es;
  void add_edge(int u,int v,T c){
    es.emplace_back(u,v,c);
    G[u].emplace_back(v);
  }

  vector<T> build(int from,int &neg_loop){
    const T INF = numeric_limits<T>::max();
    int n=G.size();
    vector<T> ds(n,INF);
    ds[from]=0;
    for(int j=0;j<n;j++){
      bool update=0;
      for(auto e:es){
        if(!reach[e.u] or !reach[e.v] or ds[e.u]==INF) continue;
        if(ds[e.v]>ds[e.u]+e.w){
          ds[e.v]=ds[e.u]+e.w;
          update=1;
        }
      }
      if(!update) break;
      if(j==n-1){
        neg_loop=1;
        return ds;
      }
    }
    neg_loop=0;
    return ds;
  }

  void dfs(int v){
    if(used[v]) return;
    used[v]=1;
    for(int u:G[v]) dfs(u);
  }

  T shortest_path(int from,int to,int &neg_loop){
    int n=G.size();
    for(int i=0;i<n;i++){
      fill(used.begin(),used.end(),0);
      dfs(i);
      reach[i]=used[to];
    }
    return build(from,neg_loop)[to];
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/GRL_1_B.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m,r;
  cin>>n>>m>>r;

  BellmanFord<int> G(n);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    G.add_edge(a,b,c);
  }

  int neg_loop;
  auto res=G.build(r,neg_loop);
  if(neg_loop) drop("NEGATIVE CYCLE");

  for(int x:res){
    if(x==numeric_limits<int>::max()) cout<<"INF\n";
    else cout<<x<<"\n";
  }
  cout<<flush;
  return 0;
}