// Dos formas equivocadas de contar peajes, para ver dónde fallan. Ninguna es correcta.
#pragma once

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

struct Road {
    int a;
    int b;
    long long length;
    bool toll;
};

struct RoadEnd {
    int to;
    long long length;
    bool toll;
};

inline std::vector<std::vector<RoadEnd>> road_lists(int cities, const std::vector<Road>& roads) {
    std::vector<std::vector<RoadEnd>> lists(static_cast<std::size_t>(cities));
    for (const Road& road : roads) {
        lists[static_cast<std::size_t>(road.a)].push_back({road.b, road.length, road.toll});
        lists[static_cast<std::size_t>(road.b)].push_back({road.a, road.length, road.toll});
    }
    return lists;
}

inline const long long NO_ROUTE = -1;

// Error: un solo contador para toda la búsqueda. Cuenta cada carretera con peaje que se mira,
// sea de la ruta que sea. Cuando llega a k, ya no se mira ninguna otra con peaje.
inline long long with_global_counter(int cities, const std::vector<Road>& roads, int source, int target, int k) {
    using Entry = std::pair<long long, int>;
    std::vector<std::vector<RoadEnd>> lists = road_lists(cities, roads);
    const long long infinity = std::numeric_limits<long long>::max();
    std::vector<long long> distance(static_cast<std::size_t>(cities), infinity);
    std::vector<bool> fixed(static_cast<std::size_t>(cities), false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    int used = 0;
    distance[static_cast<std::size_t>(source)] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (fixed[static_cast<std::size_t>(u)]) continue;
        fixed[static_cast<std::size_t>(u)] = true;
        for (const RoadEnd& end : lists[static_cast<std::size_t>(u)]) {
            if (fixed[static_cast<std::size_t>(end.to)]) continue;
            if (end.toll) {
                if (used == k) continue;
                used++;
            }
            if (d + end.length < distance[static_cast<std::size_t>(end.to)]) {
                distance[static_cast<std::size_t>(end.to)] = d + end.length;
                heap.push({distance[static_cast<std::size_t>(end.to)], end.to});
            }
        }
    }
    long long answer = distance[static_cast<std::size_t>(target)];
    return answer == infinity ? NO_ROUTE : answer;
}

// Error: cada entrada recuerda sus peajes, pero cada ciudad se fija una sola vez, con la menor
// distancia. La primera llegada a una ciudad puede haber gastado los peajes que hacían falta después.
inline long long with_one_distance_per_city(int cities, const std::vector<Road>& roads, int source, int target,
                                            int k) {
    using Entry = std::tuple<long long, int, int>;
    std::vector<std::vector<RoadEnd>> lists = road_lists(cities, roads);
    std::vector<bool> fixed(static_cast<std::size_t>(cities), false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    heap.push({0, source, 0});
    while (!heap.empty()) {
        auto [d, u, used] = heap.top();
        heap.pop();
        if (fixed[static_cast<std::size_t>(u)]) continue;
        fixed[static_cast<std::size_t>(u)] = true;
        if (u == target) return d;
        for (const RoadEnd& end : lists[static_cast<std::size_t>(u)]) {
            int next_used = used + (end.toll ? 1 : 0);
            if (next_used <= k && !fixed[static_cast<std::size_t>(end.to)]) {
                heap.push({d + end.length, end.to, next_used});
            }
        }
    }
    return NO_ROUTE;
}