// Cuánto crece Dijkstra con el número de capas, en un grafo al azar de 20 000 ciudades.
// Los conteos no dependen de la máquina. Los tiempos sí: menor de 3 intentos, con -O2.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "shortest_paths.h"
#include "state_graph.h"

int main() {
    std::mt19937 rng(505);
    const int cities = 20000;
    const int arcs = 100000;
    Graph graph(cities);
    for (int i = 0; i < arcs; i++) {
        int a = static_cast<int>(rng() % cities);
        int b = static_cast<int>(rng() % cities);
        add_arc(graph, a, b, 1 + static_cast<long long>(rng() % 1000));
    }
    std::cout << "capas    estados    sacadas  arcos mirados      ms\n";
    for (int c : {1, 2, 4, 8, 16, 32}) {
        double best = 1e18;
        WalkResult result{};
        for (int attempt = 0; attempt < 3; attempt++) {
            auto start = std::chrono::steady_clock::now();
            result = min_walk_multiple(graph, 0, 1, c);
            auto stop = std::chrono::steady_clock::now();
            best = std::min(best, std::chrono::duration<double, std::milli>(stop - start).count());
        }
        std::cout << std::setw(5) << c << std::setw(11) << cities * c << std::setw(11) << result.pops << std::setw(15)
                  << result.relaxations << std::setw(8) << std::fixed << std::setprecision(1) << best << '\n';
    }
}