558 - Wormholes uva solution

// pure bellman ford algorithm


#include <bits/stdc++.h>
using namespace std;
struct node{
    int u;
    int v;
    int w;


};

vector<node>V;
int u,v,w;
int n,m;
node temp;
int d[1009];
void input()
{
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            cin>>u>>v>>w;
            temp.u=u;
            temp.v=v;
            temp.w=w;
            V.push_back(temp);

        }

}
void ini()
{
    for(int i=0;i<=n;i++)
        d[i]=INT_MAX;
}
void belmanford(int src)
{
    d[src] = 0;

    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < m; ++j)
            if (d[V[j].u] + V[j].w < d[V[j].v])
                d[V[j].v] = d[V[j].u] + V[j].w;


}
bool negetive_cycle()
{
     for ( int j = 0; j < m; j++ )
            if ( d [V [j].u] + V [j].w < d [V [j].v] )
                return true;
    return false;
}


int main()
{

    int test;

    cin>>test;
    for(int t=1;t<=test;t++)
    {
        input();
        ini();
        belmanford(0);
        if(!negetive_cycle())
            cout<<"not possible"<<endl;
        else
            cout<<"possible"<<endl;
            V.clear();


    }

    return 0;
}

SHARE

Amit Ghosh

• 
• 
• 
• 
•