// Caminos mínimos desde un origen: Bellman-Ford en sus dos formas, la recuperación de un ciclo
// negativo, y los algoritmos con los que se compara (BFS, DAG y Dijkstra).
#pragma once

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

struct Edge {
    int from;
    int to;
    long long weight;
};

// Un valor que ningún camino alcanza, y lejos del límite de long long.
inline constexpr long long INF = std::numeric_limits<long long>::max() / 4;

inline std::size_t idx(int v) { return static_cast<std::size_t>(v); }

// La tabla completa: table[i][v] es d_i(v), el menor largo de un camino de source a v con a lo
// sumo i aristas. Tiene las filas 0, ..., rows.
inline std::vector<std::vector<long long>> bellman_ford_table(int n, const std::vector<Edge>& edges, int source,
                                                              int rows) {
    std::vector<std::vector<long long>> table(idx(rows) + 1, std::vector<long long>(idx(n), INF));
    table[0][idx(source)] = 0;
    for (int i = 1; i <= rows; i++) {
        table[idx(i)] = table[idx(i - 1)];  // el caso de a lo sumo i - 1 aristas
        for (const Edge& e : edges) {       // el caso de exactamente i aristas, con e al final
            if (table[idx(i - 1)][idx(e.from)] == INF) continue;
            const long long through = table[idx(i - 1)][idx(e.from)] + e.weight;
            if (through < table[idx(i)][idx(e.to)]) table[idx(i)][idx(e.to)] = through;
        }
    }
    return table;
}

struct BellmanFordResult {
    std::vector<long long> dist;
    std::vector<int> pred;  // pred[v] es el nodo desde el que se relajó v por última vez, o -1
    int rounds = 0;         // vueltas que se hicieron
    int witness = -1;       // un nodo relajado en la vuelta n, o -1 si no hubo ninguno
};

// Una sola fila, hasta n vueltas, y se detiene si una vuelta no cambia nada.
// Invariante: tras la vuelta i, d[v] es el largo de algún camino de source a v (o INF), y d[v] <= d_i(v).
// after_round, si se pasa, se llama al final de cada vuelta.
inline BellmanFordResult bellman_ford(int n, const std::vector<Edge>& edges, int source,
                                      const std::function<void(int, const BellmanFordResult&)>& after_round = {}) {
    BellmanFordResult result;
    result.dist.assign(idx(n), INF);
    result.pred.assign(idx(n), -1);
    result.dist[idx(source)] = 0;
    for (int round = 1; round <= n; round++) {
        result.rounds = round;
        int last_relaxed = -1;
        for (const Edge& e : edges) {
            if (result.dist[idx(e.from)] == INF) continue;  // no alcanzado: no hay nada que propagar
            if (result.dist[idx(e.from)] + e.weight < result.dist[idx(e.to)]) {
                result.dist[idx(e.to)] = result.dist[idx(e.from)] + e.weight;
                result.pred[idx(e.to)] = e.from;
                last_relaxed = e.to;
            }
        }
        if (after_round) after_round(round, result);
        if (last_relaxed == -1) break;
        if (round == n) result.witness = last_relaxed;
    }
    return result;
}

// Dado un nodo relajado en la vuelta n, devuelve un ciclo negativo: c[0], c[1], ..., con
// c[i] -> c[i + 1] aristas del grafo y c.back() -> c[0] la que lo cierra.
inline std::vector<int> recover_cycle(int n, const std::vector<int>& pred, int witness) {
    int x = witness;
    for (int step = 0; step < n; step++) x = pred[idx(x)];  // ahora x está en el ciclo
    std::vector<int> cycle;
    int y = x;
    do {
        cycle.push_back(y);
        y = pred[idx(y)];
    } while (y != x);
    // Se leyó siguiendo a los predecesores, así que está al revés.
    std::vector<int> forward(cycle.rbegin(), cycle.rend());
    return forward;
}

// El menor peso de una arista de a hacia b. Sirve para sumar un ciclo o un camino ya recuperado.
inline long long edge_weight(const std::vector<Edge>& edges, int a, int b) {
    long long best = INF;
    for (const Edge& e : edges) {
        if (e.from == a && e.to == b && e.weight < best) best = e.weight;
    }
    return best;
}

inline long long cycle_weight(const std::vector<Edge>& edges, const std::vector<int>& cycle) {
    long long total = 0;
    for (std::size_t i = 0; i < cycle.size(); i++) {
        total += edge_weight(edges, cycle[i], cycle[(i + 1) % cycle.size()]);
    }
    return total;
}

inline std::vector<std::vector<std::pair<int, long long>>> adjacency(int n, const std::vector<Edge>& edges) {
    std::vector<std::vector<std::pair<int, long long>>> adj(idx(n));
    for (const Edge& e : edges) adj[idx(e.from)].push_back({e.to, e.weight});
    return adj;
}

// BFS: sirve si todas las aristas pesan lo mismo. Cuenta aristas.
inline std::vector<long long> bfs_distances(int n, const std::vector<Edge>& edges, int source) {
    const auto adj = adjacency(n, edges);
    std::vector<long long> dist(idx(n), INF);
    std::queue<int> pending;
    dist[idx(source)] = 0;
    pending.push(source);
    while (!pending.empty()) {
        const int u = pending.front();
        pending.pop();
        for (const auto& [v, weight] : adj[idx(u)]) {
            (void)weight;
            if (dist[idx(v)] == INF) {
                dist[idx(v)] = dist[idx(u)] + 1;
                pending.push(v);
            }
        }
    }
    return dist;
}

// DAG: procesa los nodos en orden topológico, con pesos de cualquier signo. Devuelve una lista
// vacía si el grafo tiene un ciclo.
inline std::vector<long long> dag_distances(int n, const std::vector<Edge>& edges, int source) {
    const auto adj = adjacency(n, edges);
    std::vector<int> in_degree(idx(n), 0);
    for (const Edge& e : edges) in_degree[idx(e.to)]++;
    std::vector<int> order;
    for (int v = 0; v < n; v++) {
        if (in_degree[idx(v)] == 0) order.push_back(v);
    }
    std::vector<long long> dist(idx(n), INF);
    dist[idx(source)] = 0;
    for (std::size_t next = 0; next < order.size(); next++) {
        const int u = order[next];
        for (const auto& [v, weight] : adj[idx(u)]) {
            if (dist[idx(u)] != INF && dist[idx(u)] + weight < dist[idx(v)]) dist[idx(v)] = dist[idx(u)] + weight;
            if (--in_degree[idx(v)] == 0) order.push_back(v);
        }
    }
    if (order.size() != idx(n)) return {};
    return dist;
}

// Dijkstra con heap y borrado perezoso, de la semana 5. Solo es correcto con pesos no negativos: si
// hay negativos, un nodo fijado puede bajar después, pero nadie vuelve a leer sus aristas.
inline std::vector<long long> dijkstra(int n, const std::vector<Edge>& edges, int source) {
    const auto adj = adjacency(n, edges);
    std::vector<long long> dist(idx(n), INF);
    using Entry = std::pair<long long, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    std::vector<bool> settled(idx(n), false);
    dist[idx(source)] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        const int u = heap.top().second;
        heap.pop();
        if (settled[idx(u)]) continue;
        settled[idx(u)] = true;
        for (const auto& [v, weight] : adj[idx(u)]) {
            if (dist[idx(u)] + weight < dist[idx(v)]) {
                dist[idx(v)] = dist[idx(u)] + weight;
                heap.push({dist[idx(v)], v});
            }
        }
    }
    return dist;
}