// Error: un heap de nodos, cuyo comparador lee el arreglo de distancias. Relajar cambia las claves
// de lo que ya está dentro, sin que el heap se entere, y deja de cumplir su invariante.
#include <iostream>
#include <queue>
#include <vector>

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

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "uso: comparator_reads_distance mapa.txt\n";
        return 2;
    }
    Graph graph = graph_of(read_map_file(argv[1]));
    int bad_runs = 0;
    int bad_nodes = 0;
    const int runs = 200;
    for (int source = 0; source < runs; source++) {
        std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
        std::vector<bool> settled(graph.node_count(), false);
        // Una lambda que captura no tiene constructor por defecto: hay que pasarla al construir.
        auto farther = [&distance](int a, int b) { return distance[a] > distance[b]; };
        std::priority_queue<int, std::vector<int>, decltype(farther)> heap(farther);
        distance[source] = 0;
        heap.push(source);
        while (!heap.empty()) {
            int u = heap.top();
            heap.pop();
            if (settled[u]) {
                continue;
            }
            settled[u] = true;
            for (const Edge& edge : graph.neighbors(u)) {
                if (distance[u] + edge.weight < distance[edge.to]) {
                    distance[edge.to] = distance[u] + edge.weight;
                    heap.push(edge.to);
                }
            }
        }
        std::vector<Meters> right = dijkstra(graph, source).distance;
        int bad = 0;
        for (int v = 0; v < graph.node_count(); v++) {
            bad += distance[v] != right[v] ? 1 : 0;
        }
        bad_nodes += bad;
        bad_runs += bad > 0 ? 1 : 0;
    }
    std::cout << "origenes con alguna distancia equivocada: " << bad_runs << " de " << runs << "\n";
    std::cout << "distancias equivocadas en total: " << bad_nodes << "\n";
    return 0;
}