UVa : 558 :: Wormholes

Problem : Please find the problem here.

Explanation : The problem basically asks for the negative cycle in the given directed graph.

Code : Used Bellman-Ford Algorithm .

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

const int mxN = 2e3;
int n, m, d[mxN], p[mxN];
vector<array<int, 2>> adj[mxN];
bool vis[mxN];

bool bellman_ford(int src){
    d[src] = 0;

    p[src] = -1;
    vis[src] = 1;

    for(int i = 0; i < n; i++){

        for(int u = 0; u < n; u++){
	    for(int k = 0; k < (int)adj[u].size(); k++){

                array<int, 2> vv = adj[u][k];

                int v = vv[1];
		int cost = vv[0];
		if(vis[u]){
		    if(!vis[v] || ((d[u]+cost) < d[v])){
		        if(i < n-1){
			    vis[v] = 1;
			    d[v] = d[u]+cost;
		            p[v] = u;
			}
			else{

                            return true;
			}
		    }
	        }
	    }
        }
    }
    return false;
}

void init(){
    for(int i = 0; i < n; i++){
        adj[i].clear();
    }
    memset(vis, false, sizeof(vis));
    memset(p, -1, sizeof(p));
    memset(d, -1, sizeof(d));
}

int main()
{

    ofstream fout("out");
    int t;
    cin >> t;
    while(t--){

        cin >> n >> m;
	init();
	for(int i = 0, a, b, c; i < m; i++){
	    cin >> a >> b >> c;
	    adj[a].push_back({c, b});
	    //adj[b].push_back({c, a});
	}
	bool ok = bellman_ford(0);
	cout << (ok?"possible":"not possible") << '\n';
    }	
    return 0;
}