// Búsqueda exacta del viajero por backtracking, con tres formas de podar. Solo devuelve el costo y la
// cantidad de nodos visitados del árbol de búsqueda. Un recorrido parcial sale de 0 y crece por el final.
#pragma once
#include <algorithm>
#include <cstddef>
#include <limits>
#include <vector>

namespace bound {

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

inline constexpr long long NO_TOUR = std::numeric_limits<long long>::max() / 4;

inline std::size_t at(int i) { return static_cast<std::size_t>(i); }

enum class Pruning {
    none,      // recorre todo el árbol
    partial,   // poda si lo ya recorrido alcanza al mejor conocido
    spanning,  // lo ya recorrido, más una cota inferior de lo que falta
};

struct Result {
    long long cost = NO_TOUR;
    long long nodes = 0;
    bool finished = true;
};

// El peso de un árbol de expansión mínima de los nodos marcados, con Prim en O(r²).
inline long long spanning_weight(const Matrix& d, const std::vector<int>& nodes) {
    if (nodes.size() <= 1) return 0;
    std::vector<long long> best(nodes.size(), NO_TOUR);
    std::vector<char> inside(nodes.size(), 0);
    best[0] = 0;
    long long weight = 0;
    for (std::size_t round = 0; round < nodes.size(); round++) {
        std::size_t v = nodes.size();
        for (std::size_t u = 0; u < nodes.size(); u++) {
            if (inside[u] == 0 && (v == nodes.size() || best[u] < best[v])) v = u;
        }
        inside[v] = 1;
        weight += best[v];
        for (std::size_t u = 0; u < nodes.size(); u++) {
            const long long edge = d[at(nodes[v])][at(nodes[u])];
            if (inside[u] == 0 && edge < best[u]) best[u] = edge;
        }
    }
    return weight;
}

// Una cota inferior para terminar un recorrido que está en last, con los nodos de rest sin visitar.
// Cualquier forma de terminar sale de last a un nodo de rest, recorre rest en un camino y vuelve de
// un nodo de rest a 0. Ese camino es un árbol de expansión de rest, así que pesa al menos el mínimo.
inline long long completion_bound(const Matrix& d, int last, const std::vector<int>& rest) {
    if (rest.empty()) return d[at(last)][0];
    long long out = NO_TOUR;
    long long back = NO_TOUR;
    for (int r : rest) {
        out = std::min(out, d[at(last)][at(r)]);
        back = std::min(back, d[at(r)][0]);
    }
    return out + spanning_weight(d, rest) + back;
}

struct Search {
    const Matrix& d;
    Pruning pruning;
    long long node_limit;
    Result result;

    void visit(int last, std::vector<int>& rest, long long so_far) {
        if (!result.finished) return;
        result.nodes++;
        if (result.nodes > node_limit) {
            result.finished = false;
            return;
        }
        if (rest.empty()) {
            result.cost = std::min(result.cost, so_far + d[at(last)][0]);
            return;
        }
        if (pruning == Pruning::partial && so_far >= result.cost) return;
        if (pruning == Pruning::spanning && so_far + completion_bound(d, last, rest) >= result.cost) return;
        // Probar primero lo más cercano encuentra pronto un buen recorrido, y eso hace podar más.
        std::vector<int> order = rest;
        std::sort(order.begin(), order.end(), [&](int a, int b) { return d[at(last)][at(a)] < d[at(last)][at(b)]; });
        for (int next : order) {
            std::vector<int> remaining;
            remaining.reserve(rest.size() - 1);
            for (int r : rest) {
                if (r != next) remaining.push_back(r);
            }
            visit(next, remaining, so_far + d[at(last)][at(next)]);
        }
    }
};

// node_limit corta la búsqueda: finished queda en false y el costo no vale como óptimo.
inline Result solve(const Matrix& d, Pruning pruning, long long node_limit = std::numeric_limits<long long>::max()) {
    const int n = static_cast<int>(d.size());
    Search search{d, pruning, node_limit, Result{}};
    if (n <= 1) {
        search.result.cost = 0;
        return search.result;
    }
    std::vector<int> rest;
    for (int v = 1; v < n; v++) rest.push_back(v);
    search.visit(0, rest, 0);
    return search.result;
}

}  // namespace bound