Untitled

//directed weighted graph
//#include<unordered_map>
#define occ 1e8
#include<vector>
#include<list>
#include<cmath>

vector<int> bellmonFord(int n, int m, int src, vector<vector<int>> &edges) {
    /* unordered_map<int,list<pair<int,int>>> adj;
    for(int i=0;i<m;i++){
        int u=edges[i][0];
        int v=edges[i][1];
        adj[u].push_back(v);
    } */
    vector<int> dist(n+1,occ);
    dist[src]=0;

    for(int i=1;i<n;i++){ //n-1 times update
        for(int j=0;j<m;j++){
            int u=edges[j][0];
            int v=edges[j][1];
            int w=edges[j][2];
            if((dist[u]+w)<dist[v]){
                dist[v]=dist[u]+w;
            }
        }
    }
    
   /*  for(int j=0;j<m;j++){
        int u=edges[j][0];
        int v=edges[j][1];
        int w=edges[j][2];
        if(dist[u]!=occ &&((dist[u]+w) <dist[v])){
            return-1;
        }
    } */
    return dist;
  
}
/* 
The Bellman-Ford algorithm is applied n-1 times
 because it is the maximum number of edges in any shortest path of a 
 graph with n vertices. The algorithm works by iteratively relaxing the 
 edges of the graph, updating the distance estimates for each vertex. 
 After k iterations, the algorithm has found the shortest paths between 
 the source vertex and all other vertices that have at most k edges. 
 Since the longest possible shortest path in a graph with n vertices has 
 at most n-1 edges, it is sufficient to run the algorithm for n-1 iterations 
 to find the shortest paths between the source vertex and all other vertices */