Untitled

#include <bits/stdc++.h>
using namespace std;

vector<long> getOptimalFlightRates(int flight_nodes, vector<int> flight_from, vector<int> flight_to, vector<int> flight_weight, vector<vector<int>> queries) {
    // Build the adjacency list for the graph
    unordered_map<int, vector<pair<int, int>>> graph;
    int flight_edges = flight_from.size();
    
    for (int i = 0; i < flight_edges; ++i) {
        graph[flight_from[i]].emplace_back(flight_to[i], flight_weight[i]);
    }

    vector<long> results;
    
    // Process each query
    for (const auto& query : queries) {
        int start = query[0];
        int destination = query[1];
        int maxStops = query[2];
        
        // Min-heap to store (cost, current_node, current_stops)
        priority_queue<tuple<long, int, int>, vector<tuple<long, int, int>>, greater<tuple<long, int, int>>> minHeap;
        minHeap.emplace(0, start, 0); // (cost, node, stops)
        
        // Keep track of the minimum cost to reach each node with a certain number of stops
        vector<vector<long>> minCost(flight_nodes, vector<long>(maxStops + 2, LONG_MAX));
        minCost[start][0] = 0;

        long cheapestCost = LONG_MAX;

        while (!minHeap.empty()) {
            auto [currentCost, currentNode, currentStops] = minHeap.top();
            minHeap.pop();

            // If we reach the destination and within the allowed stops
            if (currentNode == destination && currentStops <= maxStops + 1) {
                cheapestCost = min(cheapestCost, currentCost);
                continue; // No need to proceed further from this node
            }

            // If we can still make more stops
            if (currentStops < maxStops + 1) {
                for (const auto& [nextNode, weight] : graph[currentNode]) {
                    long newCost = currentCost + weight;
                    // Only add to the heap if we found a cheaper way to get to nextNode with currentStops + 1
                    if (newCost < minCost[nextNode][currentStops + 1]) {
                        minCost[nextNode][currentStops + 1] = newCost;
                        minHeap.emplace(newCost, nextNode, currentStops + 1);
                    }
                }
            }
        }

        // If we found a valid cost, add it to results; otherwise, add -1
        results.push_back(cheapestCost == LONG_MAX ? -1 : cheapestCost);
    }

    return results;
}

int main() {
    // Example inputs
    int flight_nodes = 5;
    vector<int> flight_from = {0, 0, 4,4,1};
    vector<int> flight_to = {1, 4, 1, 3, 2};
    vector<int> flight_weight = {10,3,5,4,2};
    
    // Example queries: (start node, destination node, max stops)
    vector<vector<int>> queries = {
        {0,1,0},
        {0,1,1},
        {4,3,1},
        {0,2,2}
    };
    
    // Get optimal flight rates
    vector<long> results = getOptimalFlightRates(flight_nodes, flight_from, flight_to, flight_weight, queries);
    
    // Print the results
    for (long cost : results) {
        cout << cost << endl;
    }

    return 0;
}