// Camino más largo en un DAG, y los subproblemas de la semana 7 vistos como caminos.
#pragma once

#include <algorithm>
#include <string>
#include <vector>

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

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

// Orden topológico por DFS, como en la semana 6: lo que termina último va primero.
inline void visit_for_order(const WeightedDag& g, int u, std::vector<char>& seen, std::vector<int>& finished) {
    seen[u] = 1;
    for (const Arc& arc : g[u]) {
        if (!seen[arc.to]) visit_for_order(g, arc.to, seen, finished);
    }
    finished.push_back(u);
}

inline std::vector<int> topological_order(const WeightedDag& g) {
    std::vector<char> seen(g.size(), 0);
    std::vector<int> finished;
    for (int u = 0; u < static_cast<int>(g.size()); u++) {
        if (!seen[u]) visit_for_order(g, u, seen, finished);
    }
    std::reverse(finished.begin(), finished.end());
    return finished;
}

struct LongestPaths {
    std::vector<long long> length;  // solo tiene sentido si reached[v]
    std::vector<char> reached;      // hay camino desde el origen
    std::vector<int> pred;          // nodo anterior en un camino más largo, o -1
};

// Invariante: al llegar a u en el orden, ya se miraron todas las aristas que entran a u, así que
// length[u] es definitivo. De un nodo no alcanzado no se sale: no hay valor que sumarle.
inline LongestPaths longest_paths(const WeightedDag& g, int source) {
    const std::size_t n = g.size();
    LongestPaths r{std::vector<long long>(n, 0), std::vector<char>(n, 0), std::vector<int>(n, -1)};
    r.reached[source] = 1;
    for (int u : topological_order(g)) {
        if (!r.reached[u]) continue;
        for (const Arc& arc : g[u]) {
            const long long candidate = r.length[u] + arc.weight;
            if (!r.reached[arc.to] || candidate > r.length[arc.to]) {
                r.reached[arc.to] = 1;
                r.length[arc.to] = candidate;
                r.pred[arc.to] = u;
            }
        }
    }
    return r;
}

inline std::vector<int> path_to(const LongestPaths& r, int target) {
    std::vector<int> path;
    for (int v = target; v != -1; v = r.pred[v]) path.push_back(v);
    std::reverse(path.begin(), path.end());
    return path;
}

// Error: todos empiezan en 0, como si cualquier nodo fuera origen.
inline std::vector<long long> longest_from_anywhere(const WeightedDag& g) {
    std::vector<long long> length(g.size(), 0);
    for (int u : topological_order(g)) {
        for (const Arc& arc : g[u]) length[arc.to] = std::max(length[arc.to], length[u] + arc.weight);
    }
    return length;
}

// Greedy que falla: salir siempre por la arista de mayor peso. Devuelve el largo del recorrido
// si llega al destino, y escribe el recorrido en walk.
inline bool heaviest_arc_walk(const WeightedDag& g, int source, int target, long long& total, std::vector<int>& walk) {
    total = 0;
    walk = {source};
    int u = source;
    while (u != target && !g[u].empty()) {
        const Arc* best = &g[u][0];
        for (const Arc& arc : g[u]) {
            if (arc.weight > best->weight) best = &arc;
        }
        total += best->weight;
        u = best->to;
        walk.push_back(u);
    }
    return u == target;
}

// Árbitro: prueba todos los caminos desde u. Máximo en best[v] para cada v alcanzable.
inline void all_paths(const WeightedDag& g, int u, long long so_far, std::vector<long long>& best,
                      std::vector<char>& seen) {
    if (!seen[u] || so_far > best[u]) {
        seen[u] = 1;
        best[u] = so_far;
    }
    for (const Arc& arc : g[u]) all_paths(g, arc.to, so_far + arc.weight, best, seen);
}

// El grafo de subproblemas de la distancia de edición: una arista por cada casilla leída, de la
// casilla leída a la que la lee. El peso es menos el costo, para usar el camino más largo.
inline int edit_node(std::size_t i, std::size_t j, std::size_t m) {
    return static_cast<int>(i * (m + 1) + j);
}

inline WeightedDag edit_subproblem_dag(const std::string& a, const std::string& b) {
    const std::size_t n = a.size();
    const std::size_t m = b.size();
    WeightedDag g((n + 1) * (m + 1));
    for (std::size_t i = 0; i <= n; i++) {
        for (std::size_t j = 0; j <= m; j++) {
            const int here = edit_node(i, j, m);
            if (i < n) g[here].push_back({edit_node(i + 1, j, m), -1});
            if (j < m) g[here].push_back({edit_node(i, j + 1, m), -1});
            if (i < n && j < m) g[here].push_back({edit_node(i + 1, j + 1, m), a[i] == b[j] ? 0 : -1});
        }
    }
    return g;
}

// El de la mochila: un nodo por (i, c), más un origen que da a todas las casillas (0, c).
struct KnapsackObject {
    std::size_t weight;
    long long value;
};

inline long long knapsack_as_path(const std::vector<KnapsackObject>& objects, std::size_t capacity) {
    const std::size_t rows = objects.size() + 1;
    const std::size_t columns = capacity + 1;
    const auto node = [columns](std::size_t i, std::size_t c) { return static_cast<int>(i * columns + c); };
    const int source = static_cast<int>(rows * columns);
    WeightedDag g(rows * columns + 1);
    for (std::size_t c = 0; c < columns; c++) g[source].push_back({node(0, c), 0});
    for (std::size_t i = 1; i < rows; i++) {
        const KnapsackObject& object = objects[i - 1];
        for (std::size_t c = 0; c < columns; c++) {
            g[node(i - 1, c)].push_back({node(i, c), 0});
            if (object.weight <= c) g[node(i - 1, c - object.weight)].push_back({node(i, c), object.value});
        }
    }
    return longest_paths(g, source).length[node(rows - 1, capacity)];
}