Source Code Status Test Cases
    Policy: public     Reviewed: 42    
00.00 sec    3208 KB    110 lines     1970 bytes    2016-12-07 09:19
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

int V, E;
struct Edge {
  int s;
  int t;
  int cost;
};
vector<Edge> edge;
vector<int> d;
#define INF 1e9

bool bellman_ford(int s) {
  d.assign(V, INF);
  d[s] = 0;

  rep (i, V-1) {
    rep (j, E) {
      auto e = edge[j];
      auto u = e.s;
      auto v = e.t;
      if (d[u] == INF) {
        continue;
      }
      if (d[v] > d[u] + e.cost) {
        d[v] = d[u] + e.cost;
      }
    }
  }
  rep (j, E) {
    auto e = edge[j];
    auto u = e.s;
    auto v = e.t;
    if (d[u] == INF) {
      continue;
    }
    if (d[v] > d[u] + e.cost) {
      return false;
    }
  }
  return true;
}

int main() {
  int src;
  scanf("%d %d %d", &V, &E, &src);
  edge.resize(E);
  rep (i, E) {
    int s, t, d;
    scanf("%d %d %d", &s, &t, &d);
    edge[i].s = s;
    edge[i].t = t;
    edge[i].cost = d;
  }

  bool valid = bellman_ford(src);
  if (valid) {
    rep (i, V) {
      if (d[i] == INF) {
        printf("INF\n");
      } else {
        printf("%d\n", d[i]);
      }
    } 
    return 0;
  }
  printf("NEGATIVE CYCLE\n");

  return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 40/40 C++14 CPU: 00.00 sec Memory: 3208 KB Length: 1970 B 2016-12-07 09:19 2016-12-07 09:19
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3144 KB
Case #2: : Accepted 00.00 sec 3036 KB
Case #3: : Accepted 00.00 sec 3100 KB
Case #4: : Accepted 00.00 sec 3148 KB
Case #5: : Accepted 00.00 sec 3172 KB
Case #6: : Accepted 00.00 sec 3192 KB
Case #7: : Accepted 00.00 sec 3076 KB
Case #8: : Accepted 00.00 sec 3092 KB
Case #9: : Accepted 00.00 sec 3120 KB
Case #10: : Accepted 00.00 sec 3188 KB
Case #11: : Accepted 00.00 sec 3012 KB
Case #12: : Accepted 00.00 sec 3036 KB
Case #13: : Accepted 00.00 sec 3148 KB
Case #14: : Accepted 00.00 sec 3112 KB
Case #15: : Accepted 00.00 sec 3080 KB
Case #16: : Accepted 00.00 sec 3168 KB
Case #17: : Accepted 00.00 sec 3196 KB
Case #18: : Accepted 00.00 sec 3132 KB
Case #19: : Accepted 00.00 sec 3076 KB
Case #20: : Accepted 00.00 sec 3072 KB
Case #21: : Accepted 00.00 sec 3128 KB
Case #22: : Accepted 00.00 sec 3152 KB
Case #23: : Accepted 00.00 sec 3192 KB
Case #24: : Accepted 00.00 sec 3020 KB
Case #25: : Accepted 00.00 sec 3184 KB
Case #26: : Accepted 00.00 sec 3168 KB
Case #27: : Accepted 00.00 sec 3076 KB
Case #28: : Accepted 00.00 sec 3188 KB
Case #29: : Accepted 00.00 sec 3096 KB
Case #30: : Accepted 00.00 sec 3192 KB
Case #31: : Accepted 00.00 sec 3200 KB
Case #32: : Accepted 00.00 sec 3196 KB
Case #33: : Accepted 00.00 sec 3152 KB
Case #34: : Accepted 00.00 sec 3200 KB
Case #35: : Accepted 00.00 sec 3188 KB
Case #36: : Accepted 00.00 sec 3204 KB
Case #37: : Accepted 00.00 sec 3196 KB
Case #38: : Accepted 00.00 sec 3104 KB
Case #39: : Accepted 00.00 sec 3208 KB
Case #40: : Accepted 00.00 sec 3104 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags