|
1 | | -/* |
2 | | - Given cities connected by flights [from,to,price], also given src, dst, & k: |
3 | | - Return cheapest price from src to dst with at most k stops |
4 | | -
|
5 | | - Dijkstra's but modified, normal won't work b/c will discard heap nodes w/o finishing |
6 | | - Modify: need to re-consider a node if dist from source is shorter than what we recorded |
7 | | - But, if we encounter node already processed but # of stops from source is lesser, |
8 | | - Need to add it back to the heap to be considered again |
9 | | -
|
10 | | - Time: O(V^2 log V) -> V = number of cities |
11 | | - Space: O(V^2) |
12 | | -*/ |
13 | | - |
14 | 1 | classSolution { |
15 | 2 | public: |
| 3 | +/** |
| 4 | + * This function uses the Bellman-Ford algorithm to find the cheapest price from source (src) to destination (dst) |
| 5 | + * with at most k stops allowed. It iteratively relaxes the edges for k+1 iterations, updating the minimum |
| 6 | + * cost to reach each vertex. The final result is the minimum cost to reach the destination, or -1 if the |
| 7 | + * destination is not reachable within the given constraints. |
| 8 | + * |
| 9 | + * Space Complexity: O(n) - space used for the prices array. |
| 10 | + * Time Complexity: O(k * |flights|) - k iterations, processing all flights in each iteration. |
| 11 | +*/ |
16 | 12 | intfindCheapestPrice(int n, vector<vector<int>>& flights,int src,int dst,int k) { |
17 | | -// build adjacency matrix |
18 | | - vector<vector<int>>adj(n, vector<int>(n)); |
19 | | -for (int i =0; i < flights.size(); i++) { |
20 | | - vector<int> flight = flights[i]; |
21 | | - adj[flight[0]][flight[1]] = flight[2]; |
22 | | - } |
23 | | - |
24 | | -// shortest distances |
25 | | - vector<int>distances(n, INT_MAX); |
26 | | - distances[src] =0; |
27 | | -// shortest steps |
28 | | - vector<int>currStops(n, INT_MAX); |
29 | | - currStops[src] =0; |
30 | | - |
31 | | -// priority queue -> (cost, node, stops) |
32 | | - priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; |
33 | | - pq.push({0, src,0}); |
34 | | - |
35 | | -while (!pq.empty()) { |
36 | | -int cost = pq.top()[0]; |
37 | | -int node = pq.top()[1]; |
38 | | -int stops = pq.top()[2]; |
39 | | - pq.pop(); |
40 | | - |
41 | | -// if destination is reached, return cost to get here |
42 | | -if (node == dst) { |
43 | | -return cost; |
44 | | - } |
45 | | - |
46 | | -// if no more steps left, continue |
47 | | -if (stops == k +1) { |
48 | | -continue; |
49 | | - } |
50 | | - |
51 | | -// check & relax all neighboring edges |
52 | | -for (int neighbor =0; neighbor < n; neighbor++) { |
53 | | -if (adj[node][neighbor] >0) { |
54 | | -int currCost = cost; |
55 | | -int neighborDist = distances[neighbor]; |
56 | | -int neighborWeight = adj[node][neighbor]; |
57 | | - |
58 | | -// check if better cost |
59 | | -int currDist = currCost + neighborWeight; |
60 | | -if (currDist < neighborDist || stops +1 < currStops[neighbor]) { |
61 | | - pq.push({currDist, neighbor, stops +1}); |
62 | | - distances[neighbor] = currDist; |
63 | | - currStops[neighbor] = stops; |
64 | | - }elseif (stops < currStops[neighbor]) { |
65 | | -// check if better steps |
66 | | - pq.push({currDist, neighbor, stops +1}); |
67 | | - } |
68 | | - currStops[neighbor] = stops; |
| 13 | + vector<int>prices(n, INT_MAX); |
| 14 | + prices[src] =0; |
| 15 | + |
| 16 | +// Perform k+1 iterations of Bellman-Ford algorithm. |
| 17 | +for (int i =0; i < k +1; i++) { |
| 18 | + vector<int>tmpPrices(begin(prices),end(prices)); |
| 19 | + |
| 20 | +for (auto it : flights) { |
| 21 | +int s = it[0]; |
| 22 | +int d = it[1]; |
| 23 | +int p = it[2]; |
| 24 | + |
| 25 | +if (prices[s] == INT_MAX)continue; |
| 26 | + |
| 27 | +if (prices[s] + p < tmpPrices[d]) { |
| 28 | + tmpPrices[d] = prices[s] + p; |
69 | 29 | } |
70 | 30 | } |
| 31 | + prices = tmpPrices; |
71 | 32 | } |
72 | | - |
73 | | -if (distances[dst] == INT_MAX) { |
74 | | -return -1; |
75 | | - } |
76 | | -return distances[dst]; |
| 33 | +return prices[dst] == INT_MAX ? -1 : prices[dst]; |
77 | 34 | } |
78 | 35 | }; |