Untitled
unknown
c_cpp
5 months ago
3.1 kB
3
Indexable
#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; }
Editor is loading...
Leave a Comment