// Un árbol de expansión mínima no contiene los caminos mínimos, y sumar una constante
// afecta a un problema y no al otro.
#include <iostream>
#include <string>
#include <vector>

#include "mst.h"

namespace {

std::string edges_text(const std::vector<Edge>& edges) {
    std::string text;
    for (const Edge& e : edges) {
        text += std::to_string(e.u) + "-" + std::to_string(e.v) + ":" + std::to_string(e.weight) + " ";
    }
    if (!text.empty()) text.pop_back();
    return text;
}

long long distance(int n, const std::vector<Edge>& edges, int from, int to) {
    return dijkstra(n, edges, from).dist[to];
}

std::vector<Edge> add_constant(std::vector<Edge> edges, int c) {
    for (Edge& e : edges) e.weight += c;
    return edges;
}

}  // namespace

int main() {
    std::vector<Edge> triangle = {{0, 1, 2}, {1, 2, 2}, {0, 2, 3}};
    std::vector<Edge> mst = kruskal(3, triangle);
    std::vector<Edge> paths = dijkstra(3, triangle, 0).tree;
    std::cout << "Triángulo: 0-1:2 1-2:2 0-2:3\n";
    std::cout << "  árbol de expansión mínima: " << edges_text(mst) << " costo " << total_weight(mst) << "\n";
    std::cout << "  de 0 a 2 dentro de ese árbol: " << distance(3, mst, 0, 2) << "\n";
    std::cout << "  de 0 a 2 en el grafo:         " << distance(3, triangle, 0, 2) << "\n";
    std::cout << "  árbol de caminos desde 0:  " << edges_text(paths) << " costo " << total_weight(paths) << "\n";

    std::vector<Edge> square = {{0, 1, 1}, {1, 2, 1}, {0, 2, 3}, {2, 3, 2}, {1, 3, 4}};
    std::cout << "\nSumar una constante c a todas las aristas de 0-1:1 1-2:1 0-2:3 2-3:2 1-3:4\n";
    std::cout << " c  árbol de expansión mínima    costo  distancia 0 a 2  camino\n";
    for (int c : {0, 1, 2, 10}) {
        std::vector<Edge> shifted = add_constant(square, c);
        std::vector<Edge> tree = kruskal(4, shifted);
        long long direct = shifted[2].weight;
        long long by_one = shifted[0].weight + shifted[1].weight;
        long long d = distance(4, shifted, 0, 2);
        std::string route = direct < by_one ? "0-2" : (by_one < direct ? "0-1-2" : "empate");
        std::string kept;
        for (const Edge& e : tree) kept += std::to_string(e.u) + "-" + std::to_string(e.v) + " ";
        std::cout << (c < 10 ? " " : "") << c << "  " << kept << std::string(29 - kept.size(), ' ')
                  << total_weight(tree) << (total_weight(tree) < 10 ? "      " : "     ") << d
                  << (d < 10 ? "                " : "               ") << route << "\n";
    }
}