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];
    }
    
};