// Recorridos del viajero sobre una matriz de distancias simétrica: el árbol duplicado, el vecino
// más cercano y la mejora local. Un recorrido es una permutación de los nodos: del último se vuelve
// al primero. El 2-opt de aquí prefiere ser claro a ser rápido: mide el recorrido entero en cada intento.
#pragma once
#include <algorithm>
#include <cstddef>
#include <limits>
#include <numeric>
#include <vector>

namespace tour {

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

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

inline long long tour_length(const Matrix& d, const Tour& t) {
    long long total = 0;
    for (std::size_t i = 0; i < t.size(); i++) {
        total += d[at(t[i])][at(t[(i + 1) % t.size()])];
    }
    return total;
}

// El largo de una caminata abierta, en el orden dado, sin volver al inicio.
inline long long walk_length(const Matrix& d, const std::vector<int>& walk) {
    long long total = 0;
    for (std::size_t i = 0; i + 1 < walk.size(); i++) total += d[at(walk[i])][at(walk[i + 1])];
    return total;
}

// ¿Pasa exactamente una vez por cada uno de los n nodos?
inline bool is_tour(const Tour& t, int n) {
    if (t.size() != at(n)) return false;
    std::vector<char> seen(at(n), 0);
    for (int v : t) {
        if (v < 0 || v >= n || seen[at(v)] != 0) return false;
        seen[at(v)] = 1;
    }
    return true;
}

struct SpanningTree {
    std::vector<std::vector<int>> children;  // hijos de cada nodo, con la raíz en 0
    long long weight = 0;
};

// Prim en O(n²), que es lo que conviene en un grafo completo. Invariante: best[v] es la arista más
// barata desde el árbol hasta v, y from[v] su otro extremo.
inline SpanningTree minimum_spanning_tree(const Matrix& d) {
    const int n = static_cast<int>(d.size());
    const long long INF = std::numeric_limits<long long>::max();
    std::vector<long long> best(at(n), INF);
    std::vector<int> from(at(n), -1);
    std::vector<char> inside(at(n), 0);
    SpanningTree tree{std::vector<std::vector<int>>(at(n)), 0};
    if (n == 0) return tree;
    best[0] = 0;
    for (int round = 0; round < n; round++) {
        int v = -1;
        for (int u = 0; u < n; u++) {
            if (inside[at(u)] == 0 && (v == -1 || best[at(u)] < best[at(v)])) v = u;
        }
        inside[at(v)] = 1;
        tree.weight += best[at(v)];
        if (from[at(v)] != -1) tree.children[at(from[at(v)])].push_back(v);
        for (int u = 0; u < n; u++) {
            if (inside[at(u)] == 0 && d[at(v)][at(u)] < best[at(u)]) {
                best[at(u)] = d[at(v)][at(u)];
                from[at(u)] = v;
            }
        }
    }
    return tree;
}

// Recorre el árbol de ida y de vuelta: cada arista aparece dos veces, y los nodos se repiten.
inline void euler_walk_from(const SpanningTree& tree, int v, std::vector<int>& walk) {
    walk.push_back(v);
    for (int child : tree.children[at(v)]) {
        euler_walk_from(tree, child, walk);
        walk.push_back(v);
    }
}

inline std::vector<int> euler_walk(const SpanningTree& tree) {
    std::vector<int> walk;
    if (!tree.children.empty()) euler_walk_from(tree, 0, walk);
    return walk;
}

// Atajar: de cada nodo se conserva su primera aparición.
inline Tour shortcut(const std::vector<int>& walk, int n) {
    std::vector<char> seen(at(n), 0);
    Tour result;
    for (int v : walk) {
        if (seen[at(v)] == 0) {
            seen[at(v)] = 1;
            result.push_back(v);
        }
    }
    return result;
}

inline Tour double_tree(const Matrix& d) {
    const int n = static_cast<int>(d.size());
    return shortcut(euler_walk(minimum_spanning_tree(d)), n);
}

// Un greedy sin garantía de este curso: desde 0, ir siempre a la ciudad libre más cercana.
inline Tour nearest_neighbor(const Matrix& d) {
    const int n = static_cast<int>(d.size());
    std::vector<char> seen(at(n), 0);
    Tour t;
    if (n == 0) return t;
    int current = 0;
    seen[0] = 1;
    t.push_back(0);
    while (static_cast<int>(t.size()) < n) {
        int next = -1;
        for (int u = 0; u < n; u++) {
            if (seen[at(u)] == 0 && (next == -1 || d[at(current)][at(u)] < d[at(current)][at(next)])) next = u;
        }
        seen[at(next)] = 1;
        t.push_back(next);
        current = next;
    }
    return t;
}

// Un cambio de 2-opt ya aplicado: se invirtió el tramo de la posición i a la j.
struct Move {
    int i;
    int j;
    long long length_after;
};

// Mejora local hasta que ningún cambio de dos aristas acorte el recorrido. Invierte el tramo, mide
// todo otra vez y deshace si no mejoró: O(n) por intento. Devuelve los cambios aplicados.
inline std::vector<Move> two_opt_plain(const Matrix& d, Tour& t) {
    const int n = static_cast<int>(t.size());
    std::vector<Move> moves;
    long long current = tour_length(d, t);
    bool improved = true;
    while (improved) {
        improved = false;
        for (int i = 1; i + 1 < n; i++) {
            for (int j = i + 1; j < n; j++) {
                std::reverse(t.begin() + i, t.begin() + j + 1);
                const long long candidate = tour_length(d, t);
                if (candidate < current) {
                    current = candidate;
                    moves.push_back({i, j, candidate});
                    improved = true;
                } else {
                    std::reverse(t.begin() + i, t.begin() + j + 1);
                }
            }
        }
    }
    return moves;
}

// ¿Algún cambio de dos aristas acortaría el recorrido? Mira cada par de aristas sin nodos en común.
inline bool is_two_opt_local_optimum(const Matrix& d, const Tour& t) {
    const int n = static_cast<int>(t.size());
    for (int a = 0; a < n; a++) {
        for (int b = a + 2; b < n; b++) {
            if (a == 0 && b == n - 1) continue;  // las aristas comparten el nodo t[0]
            const long long now = d[at(t[at(a)])][at(t[at(a + 1)])] + d[at(t[at(b)])][at(t[at((b + 1) % n)])];
            const long long swapped = d[at(t[at(a)])][at(t[at(b)])] + d[at(t[at(a + 1)])][at(t[at((b + 1) % n)])];
            if (swapped < now) return false;
        }
    }
    return true;
}

}  // namespace tour