// Caminos mínimos en un grafo dirigido: Dijkstra con entradas viejas, y un árbitro lento.
#pragma once

#include <cstddef>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

struct Arc {
    int to;
    long long weight;
};

using Graph = std::vector<std::vector<Arc>>;

inline const long long UNREACHABLE = std::numeric_limits<long long>::max();

inline void add_arc(Graph& graph, int from, int to, long long weight) {
    graph[static_cast<std::size_t>(from)].push_back({to, weight});
}

struct Pop {
    long long distance;
    int node;
    bool stale;  // el nodo ya estaba fijado: esta entrada se ignora
};

// Una mejora de d[node], hecha al atender la entrada número pop.
struct Change {
    std::size_t pop;
    int node;
    long long value;
};

struct DijkstraResult {
    std::vector<long long> distance;
    std::vector<int> parent;
    std::vector<Pop> pops;
    std::vector<Change> changes;
};

// Invariante: todo nodo fijado tiene ya su distancia de camino mínimo, si los pesos no son negativos.
inline DijkstraResult dijkstra(const Graph& graph, int source) {
    using Entry = std::pair<long long, int>;
    std::size_t n = graph.size();
    DijkstraResult result{std::vector<long long>(n, UNREACHABLE), std::vector<int>(n, -1), {}, {}};
    std::vector<bool> fixed(n, false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    result.distance[static_cast<std::size_t>(source)] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        std::size_t index = static_cast<std::size_t>(u);
        result.pops.push_back({d, u, fixed[index]});
        if (fixed[index]) continue;
        fixed[index] = true;
        for (const Arc& arc : graph[index]) {
            std::size_t to = static_cast<std::size_t>(arc.to);
            if (d + arc.weight < result.distance[to]) {
                result.distance[to] = d + arc.weight;
                result.parent[to] = u;
                result.changes.push_back({result.pops.size() - 1, arc.to, result.distance[to]});
                heap.push({result.distance[to], arc.to});
            }
        }
    }
    return result;
}

// Idea que falla: dar por definitiva la primera distancia con la que se descubre un nodo.
// Es BFS con pesos: los nodos se atienden en el orden en que se descubrieron.
inline std::vector<long long> fix_on_discovery(const Graph& graph, int source) {
    std::vector<long long> distance(graph.size(), UNREACHABLE);
    std::queue<int> pending;
    distance[static_cast<std::size_t>(source)] = 0;
    pending.push(source);
    while (!pending.empty()) {
        int u = pending.front();
        pending.pop();
        for (const Arc& arc : graph[static_cast<std::size_t>(u)]) {
            std::size_t to = static_cast<std::size_t>(arc.to);
            if (distance[to] == UNREACHABLE) {
                distance[to] = distance[static_cast<std::size_t>(u)] + arc.weight;
                pending.push(arc.to);
            }
        }
    }
    return distance;
}

// Idea que falla: caminar desde el origen tomando siempre el arco más barato hacia un nodo
// no visitado, hasta llegar al destino o quedarse sin salida. Devuelve UNREACHABLE en ese caso.
inline long long cheapest_arc_walk(const Graph& graph, int source, int target) {
    std::vector<bool> visited(graph.size(), false);
    long long total = 0;
    int now = source;
    visited[static_cast<std::size_t>(now)] = true;
    while (now != target) {
        const Arc* best = nullptr;
        for (const Arc& arc : graph[static_cast<std::size_t>(now)]) {
            if (!visited[static_cast<std::size_t>(arc.to)] && (best == nullptr || arc.weight < best->weight)) {
                best = &arc;
            }
        }
        if (best == nullptr) return UNREACHABLE;
        total += best->weight;
        now = best->to;
        visited[static_cast<std::size_t>(now)] = true;
    }
    return total;
}

// El árbitro: relajar todas las aristas una y otra vez hasta que nada cambie.
// No elige ningún orden, y da la verdad también con pesos negativos si no hay ciclos negativos.
inline std::vector<long long> relax_until_stable(const Graph& graph, int source) {
    std::vector<long long> distance(graph.size(), UNREACHABLE);
    distance[static_cast<std::size_t>(source)] = 0;
    bool changed = true;
    while (changed) {
        changed = false;
        for (std::size_t u = 0; u < graph.size(); u++) {
            if (distance[u] == UNREACHABLE) continue;
            for (const Arc& arc : graph[u]) {
                std::size_t to = static_cast<std::size_t>(arc.to);
                if (distance[u] + arc.weight < distance[to]) {
                    distance[to] = distance[u] + arc.weight;
                    changed = true;
                }
            }
        }
    }
    return distance;
}

inline std::vector<int> path_to(const std::vector<int>& parent, int source, int target) {
    std::vector<int> reversed;
    for (int node = target; node != source; node = parent[static_cast<std::size_t>(node)]) {
        reversed.push_back(node);
    }
    reversed.push_back(source);
    return std::vector<int>(reversed.rbegin(), reversed.rend());
}