// Error: std::priority_queue sin std::greater. Saca primero lo más lejano.
#include <iostream>
#include <queue>
#include <random>
#include <vector>

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

namespace {

std::vector<Meters> farthest_first(const Graph& graph, int source) {
    std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
    std::vector<bool> settled(graph.node_count(), false);
    std::priority_queue<HeapEntry> heap;  // falta std::greater
    distance[source] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        int u = heap.top().second;
        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({distance[edge.to], edge.to});
            }
        }
    }
    return distance;
}

}  // namespace

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "uso: forgot_greater mapa.txt\n";
        return 2;
    }
    Graph graph = graph_of(read_map_file(argv[1]));
    std::vector<Meters> wrong = farthest_first(graph, 0);
    std::vector<Meters> right = dijkstra(graph, 0).distance;
    int bad = 0;
    for (int v = 0; v < graph.node_count(); v++) {
        if (wrong[v] != right[v]) {
            bad++;
        }
    }
    std::cout << "distancias equivocadas: " << bad << " de " << graph.node_count() << "\n";
    return 0;
}