Sponsored
Sponsored
In this approach, use BFS to explore all possible paths. Utilize a queue to store the current node, accumulated cost, and the number of stops made so far. The key is to traverse by layer, effectively managing the permitted stops through levels of BFS. If we reach the destination within the allowed stops, track the minimum cost.
Time Complexity: O(n * k) in the worst case when every city is connected.
Space Complexity: O(n) for storing the graph and queue.
1from collections import deque, defaultdict
2
3def find_cheapest_price(n, flights, src, dst, k):
4 adj_list = defaultdict(list)
5 for start, end, price in flights:
6 adj_list[start].append((end, price))
7
8 # (current city, current cost, remaining stops)
9 queue = deque([(src, 0, k + 1)])
10
11 min_cost = float('inf')
12
13 while queue:
14 position, cost, stops = queue.popleft()
15 if position == dst:
16 min_cost = min(min_cost, cost)
17 continue
18 if stops > 0:
19 for neighbor, price in adj_list[position]:
20 if cost + price < min_cost:
21 queue.append((neighbor, cost + price, stops - 1))
22 return min_cost if min_cost != float('inf') else -1This solution constructs a graph from the flights list using an adjacency list. For BFS, a queue keeps track of the current city, the accumulated cost to reach that city, and the number of remaining stops allowed. Traverse each city, and only append a city to the queue if doing so reduces the cost to reach it. This ensures we explore the cheapest path first, within k stops. The process continues until all nodes are explored or the cheapest path is found.
This approach leverages a modified version of Dijkstra's algorithm to explore paths from source to destination using a prioritized data structure like a min-heap. Each entry tracks not only the cumulative cost but also the number of stops taken. The algorithm ensures the shortest paths are evaluated first and skips any path with exceeding stops, thus efficiently finding the minimum cost path within allowed stops.
Time Complexity: O((n+k) log n) reflects edge processing and heap operations.
Space Complexity: O(n) taken by the adjacency list and tracking structures.
1#include <queue>
2#include <vector>
3#include <unordered_map>
4#include <limits.h>
5
using namespace std;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
unordered_map<int, vector<pair<int, int>>> adj;
for (auto f : flights) {
adj[f[0]].push_back({f[1], f[2]});
}
typedef tuple<int, int, int> T;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, src, k+1});
while (!pq.empty()) {
auto [cost, city, stops] = pq.top(); pq.pop();
if (city == dst) return cost;
if (stops > 0) {
for (auto& [nextCity, price] : adj[city]) {
pq.push({cost + price, nextCity, stops - 1});
}
}
}
return -1;
}This C++ solution utilizes a min-heap or priority queue data structure to maintain the current city, accumulated cost, and stops left. Priority ensures that cities with the smallest accumulated cost are processed first, following Dijkstra's logic but capped by the number of stops. Each step examines the target city, updating the cost and queuing potential paths until either the destination is reached within allowed stops or the queue is exhausted.