// El problema del viajero: fuerza bruta sobre las permutaciones, y Held-Karp sobre subconjuntos.
// Un subconjunto de nodos es un entero: el bit v vale 1 si v está en el subconjunto.
#pragma once

#include <algorithm>
#include <cstddef>
#include <limits>
#include <numeric>
#include <vector>

namespace tsp {

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

// Un costo que ningún recorrido alcanza. Marca que no hay arista.
inline constexpr long long NONE = std::numeric_limits<long long>::max() / 4;

inline std::size_t idx(int v) { return static_cast<std::size_t>(v); }

// El costo mínimo de un recorrido que sale de 0, pasa una vez por cada nodo y vuelve a 0.
// Prueba las (n - 1)! órdenes. Devuelve NONE si no hay recorrido.
inline long long brute_force(const Costs& cost, long long* tours = nullptr) {
    const int n = static_cast<int>(cost.size());
    if (n <= 1) return 0;
    std::vector<int> middle(idx(n - 1));
    std::iota(middle.begin(), middle.end(), 1);
    long long best = NONE;
    long long count = 0;
    do {
        count++;
        long long total = cost[0][idx(middle[0])];
        for (std::size_t i = 0; i + 1 < middle.size() && total < NONE; i++) {
            const long long step = cost[idx(middle[i])][idx(middle[i + 1])];
            total = step == NONE ? NONE : total + step;
        }
        const long long back = cost[idx(middle.back())][0];
        if (total < NONE && back < NONE) best = std::min(best, total + back);
    } while (std::next_permutation(middle.begin(), middle.end()));
    if (tours != nullptr) *tours = count;
    return best;
}

// Held-Karp. table[mask][v] es el costo mínimo de un camino que sale de 0, visita exactamente los
// nodos de mask y termina en v, con v en mask. Los bits 1, ..., n - 1 son los nodos distintos de
// 0; el nodo 0 no se guarda en mask. Por eso el bit v - 1 representa al nodo v.
inline std::vector<std::vector<long long>> held_karp_table(const Costs& cost, long long* transitions = nullptr) {
    const int n = static_cast<int>(cost.size());
    const std::size_t masks = std::size_t{1} << (n - 1);
    std::vector<std::vector<long long>> table(masks, std::vector<long long>(idx(n), NONE));
    long long count = 0;
    for (int v = 1; v < n; v++) table[std::size_t{1} << (v - 1)][idx(v)] = cost[0][idx(v)];
    // Quitar un bit da un entero menor: al llegar a mask, sus subconjuntos ya están listos.
    for (std::size_t mask = 1; mask < masks; mask++) {
        for (int v = 1; v < n; v++) {
            const std::size_t bit_v = std::size_t{1} << (v - 1);
            if ((mask & bit_v) == 0 || mask == bit_v) continue;
            const std::size_t without_v = mask ^ bit_v;
            for (int u = 1; u < n; u++) {
                if ((without_v & (std::size_t{1} << (u - 1))) == 0) continue;
                count++;
                if (table[without_v][idx(u)] == NONE || cost[idx(u)][idx(v)] == NONE) continue;
                table[mask][idx(v)] = std::min(table[mask][idx(v)], table[without_v][idx(u)] + cost[idx(u)][idx(v)]);
            }
        }
    }
    if (transitions != nullptr) *transitions = count;
    return table;
}

// El costo del mejor recorrido: se elige el último nodo antes de volver a 0.
inline long long held_karp(const Costs& cost, long long* transitions = nullptr) {
    const int n = static_cast<int>(cost.size());
    if (n <= 1) return 0;
    const auto table = held_karp_table(cost, transitions);
    const std::size_t masks = table.size();
    long long best = NONE;
    for (int v = 1; v < n; v++) {
        if (table[masks - 1][idx(v)] != NONE && cost[idx(v)][0] != NONE) {
            best = std::min(best, table[masks - 1][idx(v)] + cost[idx(v)][0]);
        }
    }
    return best;
}

}  // namespace tsp