// Dijkstra con std::priority_queue. En el laboratorio lo escriben con su propio MinHeap.
#ifndef SHORTEST_PATHS_H
#define SHORTEST_PATHS_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

#include "graph.h"

// 64 bits: dos aristas de 2 000 000 000 ya no caben en un int.
using Meters = std::int64_t;

// Distancia de un nodo al que no se llega. Nunca se le suma nada: solo se suma desde un nodo sacado.
const Meters UNREACHABLE = std::numeric_limits<Meters>::max();

// Distancia primero: std::pair compara por first y, si empatan, por second.
using HeapEntry = std::pair<Meters, int>;
using MinFirstQueue = std::priority_queue<HeapEntry, std::vector<HeapEntry>, std::greater<HeapEntry>>;

struct DijkstraCounts {
    std::size_t settled = 0;     // nodos que salieron con su distancia definitiva
    std::size_t pushes = 0;      // entradas que entraron al heap
    std::size_t stale = 0;       // entradas viejas, ignoradas al sacarlas
    std::size_t edges_read = 0;  // entradas de listas leídas
    std::size_t peak_heap = 0;   // el mayor tamaño que tuvo el heap
};

struct DijkstraResult {
    std::vector<Meters> distance;  // UNREACHABLE si no se llega
    std::vector<int> parent;       // -1 si no se llega, y el origen es su propio padre
    DijkstraCounts counts;
};

// Requiere pesos no negativos.
inline DijkstraResult dijkstra(const Graph& graph, int source) {
    int n = graph.node_count();
    DijkstraResult result{std::vector<Meters>(n, UNREACHABLE), std::vector<int>(n, -1), {}};
    std::vector<bool> settled(n, false);
    MinFirstQueue heap;
    result.distance[source] = 0;
    result.parent[source] = source;
    heap.push({0, source});
    result.counts.pushes++;
    result.counts.peak_heap = 1;
    while (!heap.empty()) {
        int u = heap.top().second;
        heap.pop();
        if (settled[u]) {  // entrada vieja: ya salió con una distancia menor
            result.counts.stale++;
            continue;
        }
        settled[u] = true;
        result.counts.settled++;
        for (const Edge& edge : graph.neighbors(u)) {
            result.counts.edges_read++;
            Meters through_u = result.distance[u] + edge.weight;
            if (through_u < result.distance[edge.to]) {  // relajar la arista
                result.distance[edge.to] = through_u;
                result.parent[edge.to] = u;
                heap.push({through_u, edge.to});
                result.counts.pushes++;
                result.counts.peak_heap = std::max(result.counts.peak_heap, heap.size());
            }
        }
    }
    return result;
}

// Suma los pesos de un camino. El camino tiene que usar aristas que existan.
inline Meters path_meters(const Graph& graph, const std::vector<int>& path) {
    Meters total = 0;
    for (std::size_t i = 1; i < path.size(); i++) {
        bool found = false;
        for (const Edge& edge : graph.neighbors(path[i - 1])) {
            if (edge.to == path[i]) {
                total += edge.weight;
                found = true;
                break;
            }
        }
        assert(found);
    }
    return total;
}

#endif