// ¿Sirve sumar una constante a todos los pesos? Cambia cuál camino gana.
#include <iostream>
#include <vector>

#include "shortest_paths.h"

namespace {

long long path_weight(const Graph& graph, const std::vector<int>& path) {
    long long total = 0;
    for (std::size_t i = 0; i + 1 < path.size(); i++) {
        long long best = UNREACHABLE;
        for (const Arc& arc : graph[static_cast<std::size_t>(path[i])]) {
            if (arc.to == path[i + 1] && arc.weight < best) best = arc.weight;
        }
        total += best;
    }
    return total;
}

void print_path(const std::vector<int>& path) {
    for (int node : path) std::cout << node << ' ';
}

}  // namespace

int main() {
    Graph graph(4);
    add_arc(graph, 0, 1, 1);
    add_arc(graph, 0, 2, 4);
    add_arc(graph, 2, 1, -5);
    add_arc(graph, 1, 3, 2);

    const long long shift = 5;
    Graph shifted(4);
    for (std::size_t u = 0; u < graph.size(); u++) {
        for (const Arc& arc : graph[u]) {
            add_arc(shifted, static_cast<int>(u), arc.to, arc.weight + shift);
        }
    }

    DijkstraResult result = dijkstra(shifted, 0);
    std::vector<int> chosen = path_to(result.parent, 0, 3);
    std::vector<int> real = {0, 2, 1, 3};
    std::cout << "se suma " << shift << " a cada peso\n";
    std::cout << "camino que gana tras sumar: ";
    print_path(chosen);
    std::cout << " pesa " << path_weight(shifted, chosen) << " con la suma, " << path_weight(graph, chosen)
              << " sin ella\n";
    std::cout << "camino mínimo original:     ";
    print_path(real);
    std::cout << " pesa " << path_weight(shifted, real) << " con la suma, " << path_weight(graph, real)
              << " sin ella\n";
    std::cout << "árbitro, grafo original, distancia a 3: " << relax_until_stable(graph, 0)[3] << '\n';
}