Shortest path : Bellman Ford - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

const int N = 107; // number of nodes
const int M = 1e4+7; // number of edges 
const ll inf = 1e18;

vector<int> pr(N);
vector<ll> d(N);

struct e {
   int a,b,w;
   e() {
      a = b = w = 0;
   }
   e(int _a, int _b, int _w) {
      a = _a;
      b = _b;
      w = _w;
   }
};

vector<e> edge(M);

int n,m;

int main() {
   SaveTime
   cin >> n >> m;
   for (int i = 0; i < m; i++) {
      int a,b,w; cin >> a >> b >> w;
      edge[i] = e(a,b,w);
   }
   d.assign(N, inf);
   pr.assign(N, -1);
   d[1] = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         int a = edge[j].a, b = edge[j].b, w = edge[j].w;
         if (d[a] < inf && d[a] + w < d[b]) {
            d[b] = d[a] + w;
            pr[b] = a;
         }
      }
   }
   // Check negative cycle
   bool negCycle = false;
   for (int i = 0; i < m; i++) {
      int a = edge[i].a, b = edge[i].b, w = edge[i].w;
      if (d[a] + w < d[b]) {
         negCycle = true;
      }
   }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 30000
#define pi pair<int,int>
int n,m,s=1,u,v,w;
vector<pair<int,int> > G[101];
int d[101];

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<m;++i){
        cin >> u >> v >> w;
        G[u].push_back({w,v});
    }
    for(int i=1;i<=n;++i){
        if(i==s)
            d[i]=0;
        else
            d[i]=INF;
    }
    priority_queue<pi, vector<pi> , greater<pi> > pq;
    pq.push({0,s});
    while(!pq.empty()){
        int w=pq.top().first,v=pq.top().second;
        pq.pop();
        for(pi p : G[v]){
            if(d[p.second]>d[v]+p.first){
                d[p.second]=d[v]+p.first;
                pq.push({d[p.second],p.second});
            }
        }
    }
    for(int i=1;i<=n;++i) cout << d[i] << ' ';
}