bellmanford.cpp

#include<bits/stdc++.h>
using namespace std;
int inf=INT_MAX;
vector< pair<int,int> >edge;
int w[205][205];
int b[205];
int dist[205];

int n,m;

void bellman(int s)
{
    dist[s]=0;
    for(int i=1; i<=n-1; i++)
    {
        for(int j=0; j<edge.size(); j++)
        {
            int x=edge[j].first;
            int y=edge[j].second;
            int z=w[x][y];
            //cout<<z<<endl;
            if( (dist[x] + z) < dist[y])
            {
                dist[y] = dist[x] + z;
            }
        }
    }
    for(int j=0; j<m; j++)
    {
        int x=edge[j].first;
        int y=edge[j].second;
        int z=w[x][y];
        if((dist[x] + z) < dist[y] )
        {
          
          printf("Negative cycle found\n");
        }
    }


}
int main()
{
   
        edge.clear();
        for(int i=0; i<205; i++)
        {
            for(int j=0; j<205; j++)
            {
                w[i][j]=inf;
                b[i]=0;
                
                dist[i]=inf;
            }

        }


        scanf("%d",&n);
       
        scanf("%d",&m);
        for(int i=0; i<m; i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
           
            
            edge.push_back( make_pair(x,y) );
            w[x][y]=z;


        }


        bellman(0);
  for(int i=0;i<n;i++){
    printf("%d ",dist[i]);
  }
       


    
}