Negative Cycle Finding (Bellman Ford Algorithm)

/**
 * Author     : Dipu Kumar Mohanto (Dip)
 *              BRUR
 * Problem    : 558 - Wormholes
 * Category   : Negative Cycle Finding (Bellman Ford Algorithm)
 * OJ         : UVA
 * Verdict    : Accepted
 * Date       : 06-10-2016
 **/

#include <bits/stdc++.h>

using namespace std;

#define N 10000
const int INF = 0x3f3f3f;

struct Edge {
    int u, v, w;
};

vector<Edge> G;
int dis[N];
int node, ver;

bool NegCycle(int s) {
    memset(dis, INF, sizeof(dis));

    dis[s] = 0;

    for (int i=0; i<node-1; i++) {
        for (Edge e : G) {
            int u = e.u;
            int v = e.v;
            int w = e.w;

            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
    for (int i=0; i<ver; i++) {
        int u = G[i].u;
        int v = G[i].v;
        int w = G[i].w;

        if (dis[v] > dis[u] + w)
            return 1;
    }
    return 0;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int tc;
    cin >> tc;

    while (tc--) {
        cin >> node >> ver;

        for (int i=0; i<ver; i++) {
            int x, y, z;

            cin >> x >> y >> z;

            Edge get;

            get.u = x;
            get.v = y;
            get.w = z;

            G.push_back(get);
        }

        bool f = NegCycle(0);

        if (f == 1)
            cout << "possible\n";
        else
            cout << "not possible\n";

        G.clear();
    }
}