// Floyd-Warshall: la matriz vuelta por vuelta, el ciclo de k por dentro, la diagonal y el crecimiento
// de los valores cuando hay un ciclo negativo y no se detiene.
#include <cstdio>
#include <limits>
#include <random>
#include <vector>

#include "all_pairs.h"

namespace {

void print_matrix(const Matrix& d) {
    for (const auto& row : d) {
        for (long long x : row) {
            if (x >= INF) {
                std::printf("%5s", "inf");
            } else {
                std::printf("%5lld", x);
            }
        }
        std::printf("\n");
    }
}

// Sin guardia, en double para ver el tamaño sin que haya overflow de enteros.
void growth_without_guard(int n) {
    std::vector<std::vector<double>> d(idx(n), std::vector<double>(idx(n), -1));
    for (int i = 0; i < n; i++) d[idx(i)][idx(i)] = 0;
    const double limit = static_cast<double>(std::numeric_limits<long long>::max());
    bool passed = false;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                const double through = d[idx(i)][idx(k)] + d[idx(k)][idx(j)];
                if (through < d[idx(i)][idx(j)]) d[idx(i)][idx(j)] = through;
            }
        }
        double lowest = 0;
        for (const auto& row : d) {
            for (double x : row) {
                if (x < lowest) lowest = x;
            }
        }
        if (k < 6 || (!passed && -lowest > limit)) {
            std::printf("  tras la vuelta k = %2d: menor valor %.3e%s\n", k, lowest,
                        -lowest > limit ? "  (ya no cabe en long long)" : "");
        }
        if (-lowest > limit) passed = true;
    }
}

}  // namespace

int main() {
    const int n = 4;
    const std::vector<Edge> edges = {{0, 1, 4}, {0, 3, 9}, {1, 2, -2}, {2, 3, 1}, {3, 1, 5}, {2, 0, 3}};
    std::printf("Aristas: 0->1 (4), 0->3 (9), 1->2 (-2), 2->3 (1), 3->1 (5), 2->0 (3)\n");
    Matrix d = initial_matrix(n, edges);
    std::printf("d_0, sin nodos intermedios:\n");
    print_matrix(d);
    for (int k = 0; k < n; k++) {
        floyd_round(d, n, k);
        std::printf("d_%d, tras permitir el nodo %d:\n", k + 1, k);
        print_matrix(d);
    }

    const std::vector<Edge> trap = {{1, 3, 5}, {3, 2, 5}, {2, 0, 9}, {1, 0, 30}};
    std::printf("\nEl ciclo de k por dentro. Aristas: 1->3 (5), 3->2 (5), 2->0 (9), 1->0 (30)\n");
    const Matrix right = floyd_warshall(n, trap).dist;
    const Matrix wrong = floyd_warshall_k_inside(n, trap);
    std::printf("k por fuera:\n");
    print_matrix(right);
    std::printf("k por dentro:\n");
    print_matrix(wrong);

    std::printf("\nGrafos al azar en los que k por dentro se equivoca (20000 por fila, 35 %% de aristas, pesos 1 a 9):\n");
    std::mt19937 gen(10);
    for (int size : {3, 4, 5, 8}) {
        int bad = 0;
        for (int t = 0; t < 20000; t++) {
            std::vector<Edge> random_edges;
            for (int a = 0; a < size; a++) {
                for (int b = 0; b < size; b++) {
                    if (a != b && gen() % 100 < 35) random_edges.push_back({a, b, static_cast<long long>(gen() % 9) + 1});
                }
            }
            if (floyd_warshall(size, random_edges).dist != floyd_warshall_k_inside(size, random_edges)) bad++;
        }
        std::printf("  n = %d: %d\n", size, bad);
    }

    std::printf("\nLa diagonal. Aristas: 0->1 (1), 1->2 (-3), 2->1 (2), 2->3 (1)\n");
    const std::vector<Edge> negative = {{0, 1, 1}, {1, 2, -3}, {2, 1, 2}, {2, 3, 1}};
    Matrix m = initial_matrix(n, negative);
    for (int k = 0; k < n; k++) {
        std::printf("  antes de k = %d, diagonal:", k);
        for (int v = 0; v < n; v++) std::printf(" %lld", m[idx(v)][idx(v)]);
        std::printf("\n");
        if (m[idx(k)][idx(k)] < 0) {
            std::printf("  d[%d][%d] < 0: hay un ciclo negativo, y se detiene\n", k, k);
            break;
        }
        floyd_round(m, n, k);
    }

    std::printf("\nSin detenerse: 40 nodos, todas las aristas de peso -1.\n");
    growth_without_guard(40);
}