# Bellman-Ford Algorithm

```#include<bits/stdc++.h>
#define ll long long

// compute shortest paths from 1 source to every vertices
// negative weight - tolerant
struct BellmanFord {
// NOTE:
//      vertices are ZERO-indexed
//      DIRECTIONAL graph
int n, m;
ll *dist;
int starter;
pair< pair<int, int>, int> *edges;
int cnt_edge;
ll INF;
bool computed;

void init(int n_, int m_, int starter_) {
n = n_;
m = m_;
starter = starter_;
computed = 0;

INF = 1; INF = INF * oo * oo;

dist = new ll [n+1];

for (int i = 0; i <= n; ++i) {

if (i == starter)
dist[i] = 0;
else
dist[i] = INF;
}

edges = new pair< pair<int, int>, int> [m];
cnt_edge = 0;
}

void addEdge(int u, int v, int w) {
edges[cnt_edge++] = make_pair(make_pair(u, v), w);
}

void computeShortestPaths() {
int u, v, w;

// compute shortest paths
for (int i = 1; i < n; ++i) {
for (int j = 0; j < cnt_edge; ++j) {
u = edges[j].first.first;
v = edges[j].first.second;
w = edges[j].second;
if (dist[u] != INF && dist[v] > dist[u] + w)
dist[v] = dist[u] + w;
}
}

// detect negative cycle
for (int i = 1; i < n; ++i) {
for (int j = 0; j < cnt_edge; ++j) {
u = edges[j].first.first;
v = edges[j].first.second;
w = edges[j].second;

if (dist[u] != INF && dist[v] != -INF && dist[v] > dist[u] + w)
dist[v] = -INF;
}
}
}

ll distanceTo(int v) {
if (!computed) {
computeShortestPaths();
computed = 1;
}

return dist[v];
}

};
```