// Caminos mínimos entre todos los pares: Floyd-Warshall bien escrito, con el ciclo de k por dentro,
// y correr un algoritmo de un origen V veces.
#pragma once

#include <cstddef>
#include <vector>

#include "shortest_paths.h"

using Matrix = std::vector<std::vector<long long>>;

// El estado inicial, d_0: sin nodos intermedios.
inline Matrix initial_matrix(int n, const std::vector<Edge>& edges) {
    Matrix d(idx(n), std::vector<long long>(idx(n), INF));
    for (int v = 0; v < n; v++) d[idx(v)][idx(v)] = 0;
    for (const Edge& e : edges) {
        if (e.weight < d[idx(e.from)][idx(e.to)]) d[idx(e.from)][idx(e.to)] = e.weight;
    }
    return d;
}

struct FloydResult {
    Matrix dist;
    bool negative_cycle = false;  // si es verdadero, dist quedó a medias y no significa nada
};

// Una vuelta: permite k como nodo intermedio. Convierte d_k en d_{k + 1}, en el mismo lugar.
inline void floyd_round(Matrix& d, int n, int k) {
    for (int i = 0; i < n; i++) {
        if (d[idx(i)][idx(k)] == INF) continue;
        for (int j = 0; j < n; j++) {
            if (d[idx(k)][idx(j)] == INF) continue;
            const long long through = d[idx(i)][idx(k)] + d[idx(k)][idx(j)];
            if (through < d[idx(i)][idx(j)]) d[idx(i)][idx(j)] = through;
        }
    }
}

// Antes de cada vuelta mira la diagonal: si d[k][k] < 0, hay un ciclo negativo y se detiene.
// Por eso los valores no crecen sin control.
inline FloydResult floyd_warshall(int n, const std::vector<Edge>& edges) {
    FloydResult result;
    result.dist = initial_matrix(n, edges);
    for (int k = 0; k < n; k++) {
        if (result.dist[idx(k)][idx(k)] < 0) {
            result.negative_cycle = true;
            return result;
        }
        floyd_round(result.dist, n, k);
    }
    return result;
}

// El error de esta semana: compila, termina y da números creíbles.
inline Matrix floyd_warshall_k_inside(int n, const std::vector<Edge>& edges) {
    Matrix d = initial_matrix(n, edges);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (d[idx(i)][idx(k)] == INF || d[idx(k)][idx(j)] == INF) continue;
                const long long through = d[idx(i)][idx(k)] + d[idx(k)][idx(j)];
                if (through < d[idx(i)][idx(j)]) d[idx(i)][idx(j)] = through;
            }
        }
    }
    return d;
}

// Todos los pares con V corridas de un algoritmo de un origen. El de Bellman-Ford supone que
// no hay ciclos negativos, o devuelve la fila tal como quedó.
inline Matrix all_pairs_dijkstra(int n, const std::vector<Edge>& edges) {
    Matrix d;
    for (int s = 0; s < n; s++) d.push_back(dijkstra(n, edges, s));
    return d;
}

inline Matrix all_pairs_bellman_ford(int n, const std::vector<Edge>& edges) {
    Matrix d;
    for (int s = 0; s < n; s++) d.push_back(bellman_ford(n, edges, s).dist);
    return d;
}