// Error: detener Dijkstra al meter el destino al heap, como se detenía BFS en la semana 14.
// Uso: stop_at_push [mapa.txt]
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

#include "../map_file.h"
#include "../shortest_paths.h"

namespace {

Meters stop_when(const Graph& graph, int source, int target, bool at_push) {
    int n = graph.node_count();
    std::vector<Meters> distance(n, UNREACHABLE);
    MinFirstQueue heap;
    distance[source] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (d != distance[u]) {
            continue;
        }
        if (!at_push && u == target) {
            return d;  // al sacarlo
        }
        for (const Edge& edge : graph.neighbors(u)) {
            if (d + edge.weight < distance[edge.to]) {
                distance[edge.to] = d + edge.weight;
                if (at_push && edge.to == target) {
                    return distance[target];  // demasiado pronto
                }
                heap.push({distance[edge.to], edge.to});
            }
        }
    }
    return distance[target];
}

}  // namespace

int main(int argc, char* argv[]) {
    Graph tiny(3);
    tiny.add_edge(0, 2, 5);
    tiny.add_edge(0, 1, 1);
    tiny.add_edge(1, 2, 1);
    std::cout << "de 0 a 2, al meter: " << stop_when(tiny, 0, 2, true) << ", al sacar: " << stop_when(tiny, 0, 2, false)
              << "\n";
    if (argc != 2) {
        return 0;
    }
    Graph graph = graph_of(read_map_file(argv[1]));
    std::mt19937 random(15);
    int wrong = 0;
    Meters worst = 0;
    const int pairs = 1000;
    for (int i = 0; i < pairs; i++) {
        int source = static_cast<int>(random() % graph.node_count());
        int target = static_cast<int>(random() % graph.node_count());
        Meters early = stop_when(graph, source, target, true);
        Meters right = stop_when(graph, source, target, false);
        if (early != right) {
            wrong++;
            worst = std::max(worst, early - right);
        }
    }
    std::cout << "en el mapa, " << wrong << " de " << pairs << " pares dan una distancia equivocada\n";
    std::cout << "la peor sobra " << worst << " metros\n";
    return 0;
}