558 - Wormholes Solution.

Problem Link: here

Problem Solution: একটি গ্রাফে নেগেটিভ সাইকেল আছে কিনা যাচাই করতে হবে।

code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pip pair<int,pii>
vector <pip> edge;
int node,e;
int dis[10000];
void Bellman()
{
    int i;
    for (i=0; i<node-1; i++)
    {
        int j;
        for (j=0; j<edge.size(); j++)
        {
            int u = edge[j].second.first;
            int v = edge[j].second.second;
            int w = edge[j].first;
            if (dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
            }
        }
    }
    return;
}

bool test()
{
    for (int j=0; j<edge.size(); j++)
        {
            int u = edge[j].second.first;
            int v = edge[j].second.second;
            int w = edge[j].first;
            if (dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                return true;
            }
        }
        return false;
}

int main()
{
    int tc;
    scanf("%d",&tc);
    while(tc--)
    {
        scanf("%d %d",&node,&e);
        int i;
        for (i=0; i<e; i++)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            edge.push_back(pip(cost,pii(u,v)));
        }
        for (i=0; i<node; i++)
        {
            dis[i]=10000000;
        }
        dis[0]=0;
        Bellman();
        if (test()) cout<<"possible"<<endl;
        else cout<<"not possible"<<endl;
        edge.clear();
    }
    return 0;
}