Warshall-Floyd Algorithm

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

// compute shortest paths between any pair of vertices
// negative weight - tolerant
struct WarshallFloyd {
        // NOTE:
        // vertices can be both ZERO-indexed or ONE-indexed
        // DIRECTIONAL graph
        int n;
        ll **dist;
        ll INF;    
        
        void init(int n_) {
                n = n_;
                dist = new ll *[n+1];
                INF = 1; INF = INF * oo * oo;
                
                for (int i = 0; i <= n; ++i) {
                        dist[i] = new ll[n+1];
                }
                
                for (int i = 0; i <= n; ++i)
                        for (int j = 0; j <= n; ++j) {
                                
                                if (i == j)
                                        dist[i][j] = 0;
                                else
                                        dist[i][j] = INF;
                        }
                
        }
        
        void addEdge(int u, int v, int w) {
                if (dist[u][v] > w)
                        dist[u][v] = w;
        }
        
        void computeShortestPaths() {
                
                // compute shortest paths
                for (int k = 0; k <= n; ++k)
                        for (int i = 0; i <= n; ++i)
                                for (int j = 0; j <= n; ++j)
                                        if (dist[i][k] != INF && dist[k][j] != INF &&
                                                dist[i][k] + dist[k][j] < dist[i][j])
                                                dist[i][j] = dist[i][k] + dist[k][j];
                
                // detect negative cycle
                for(int i = 0; i <= n; ++i)
                        for (int j = 0; j <= n; ++j)
                                for (int k = 0; k <= n; ++k)
                                        if (dist[k][k] < 0 && dist[i][k] != INF && dist[k][j] != INF)
                                                dist[i][j] = -INF;
        }
        
        ll getDistance(int u, int v) {
                return dist[u][v];
        }
    
};