Bellman ford algorithm(negative cycle finding)

UVa-p558.cpp

#include <iostream>
#include <vector>
using namespace std;

const int inf = 1e8;

int main()
{
    int tcc; 
    
    cin >> tcc;
    while(tcc--) {
        int n, m, u, v, wt;
        cin >> n >> m;
        vector< pair< int, int > > edges;
        int cost[n + 1][n + 1];
        
        for(int i = 0; i < m; i++) {
            cin >> u >> v >> wt;
            edges.push_back( {u, v} ); // u -> v
            cost[u][v] = wt;
        }

        int dist[n + 1];
        for(int i = 0; i < n + 1; i++) dist[i] = inf;
        dist[0] = 0; 

        for(int i = 0; i < n - 1; i++) {
            for(pair< int, int > x: edges){
                int ut = x.first, vt = x.second;
                if( dist[vt] > dist[ut] + cost[ut][vt] ){
                    dist[vt] = dist[ut] + cost[ut][vt];
                }
            }
        }

        bool flag = false;

        for(pair< int, int > x: edges) {
            int ut = x.first, vt = x.second;
            if( dist[vt] > dist[ut] + cost[ut][vt] ){
                cout << "possible\n";
                flag = true;
                break;
            }
        }

        if( !flag ){
            cout << "not possible\n";
        }

        edges.clear();
    }

    return 0;
}