// Los dos errores de partir de un "infinito" y sumarle algo a un nodo no alcanzado.
// El primero es un overflow de int: es comportamiento indefinido, y aquí lo señala el sanitizer.
#include <climits>
#include <iostream>
#include <vector>

#include "shortest_paths.h"

namespace {

void print_row(const char* name, const std::vector<long long>& row) {
    std::cout << name;
    for (long long x : row) std::cout << ' ' << (x >= INF ? "inf" : std::to_string(x));
    std::cout << '\n';
}

// Primer error: INT_MAX como infinito, sin mirar si el nodo fue alcanzado.
std::vector<int> relax_with_int_max(int n, const std::vector<Edge>& edges, int source) {
    std::vector<int> d(idx(n), INT_MAX);
    d[idx(source)] = 0;
    for (int round = 1; round < n; round++) {
        for (const Edge& e : edges) {
            if (d[idx(e.from)] + static_cast<int>(e.weight) < d[idx(e.to)]) {  // overflow si d[e.from] es INT_MAX
                d[idx(e.to)] = d[idx(e.from)] + static_cast<int>(e.weight);
            }
        }
    }
    return d;
}

// Segundo error: un infinito sin overflow, pero tampoco se trata como especial.
std::vector<long long> relax_without_check(int n, const std::vector<Edge>& edges, int source, bool& changed_last) {
    const long long big = 1'000'000'000'000;
    std::vector<long long> d(idx(n), big);
    d[idx(source)] = 0;
    changed_last = false;
    for (int round = 1; round <= n; round++) {
        changed_last = false;
        for (const Edge& e : edges) {
            if (d[idx(e.from)] + e.weight < d[idx(e.to)]) {
                d[idx(e.to)] = d[idx(e.from)] + e.weight;
                changed_last = true;
            }
        }
    }
    return d;
}

}  // namespace

int main() {
    // El origen es 0, que solo llega a 1. Los nodos 2 y 3 no se alcanzan.
    const std::vector<Edge> positive = {{2, 3, 5}, {0, 1, 7}};
    std::cout << "Primer error: INT_MAX como infinito. Aristas 2->3 (5), 0->1 (7).\n";
    std::vector<int> wrong = relax_with_int_max(4, positive, 0);
    std::cout << "d con INT_MAX:";
    for (int x : wrong) std::cout << ' ' << x;
    std::cout << '\n';
    print_row("correcto:     ", bellman_ford(4, positive, 0).dist);

    std::cout << "\nSegundo error: infinito + un negativo. Aristas 0->1 (7), 2->3 (-5).\n";
    const std::vector<Edge> negative = {{0, 1, 7}, {2, 3, -5}};
    bool changed = false;
    print_row("sin revisar:  ", relax_without_check(4, negative, 0, changed));
    print_row("revisando:    ", bellman_ford(4, negative, 0).dist);

    std::cout << "\nY un falso ciclo: 0->1 (7), y el ciclo 2->3 (-5), 3->2 (1), que el origen no alcanza.\n";
    const std::vector<Edge> unreachable = {{0, 1, 7}, {2, 3, -5}, {3, 2, 1}};
    relax_without_check(4, unreachable, 0, changed);
    std::cout << "sin revisar: la vuelta 4 cambió algo: " << (changed ? "sí" : "no") << '\n';
    const BellmanFordResult r = bellman_ford(4, unreachable, 0);
    std::cout << "revisando:   la vuelta 4 cambió algo: " << (r.witness != -1 ? "sí" : "no") << '\n';
}