1+ /* *
2+ This function uses the Bellman-Ford algorithm to find the cheapest price from source (src) to destination (dst)
3+ with at most k stops allowed. It iteratively relaxes the edges for k+1 iterations, updating the minimum
4+ cost to reach each vertex. The final result is the minimum cost to reach the destination, or -1 if the
5+ destination is not reachable within the given constraints.
6+
7+ Space Complexity: O(n) - space used for the prices array.
8+ Time Complexity: O(k * |flights|) - k iterations, processing all flights in each iteration.
9+ */
110class Solution {
211public:
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- */
1212int findCheapestPrice (int n, vector<vector<int >>& flights,int src,int dst,int k) {
1313 vector<int >prices (n, INT_MAX);
1414 prices[src] =0 ;
@@ -33,3 +33,83 @@ class Solution {
3333return prices[dst] == INT_MAX ? -1 : prices[dst];
3434 }
3535};
36+
37+
38+ /*
39+ Given cities connected by flights [from,to,price], also given src, dst, & k:
40+ Return cheapest price from src to dst with at most k stops
41+
42+ Dijkstra's but modified, normal won't work b/c will discard heap nodes w/o finishing
43+ Modify: need to re-consider a node if dist from source is shorter than what we recorded
44+ But, if we encounter node already processed but # of stops from source is lesser,
45+ Need to add it back to the heap to be considered again
46+
47+ Time: O(V^2 log V) -> V = number of cities
48+ Space: O(V^2)
49+ */
50+
51+ class Solution {
52+ public:
53+ int findCheapestPrice (int n, vector<vector<int >>& flights,int src,int dst,int k) {
54+ // build adjacency matrix
55+ vector<vector<int >>adj (n, vector<int >(n));
56+ for (int i =0 ; i < flights.size (); i++) {
57+ vector<int > flight = flights[i];
58+ adj[flight[0 ]][flight[1 ]] = flight[2 ];
59+ }
60+
61+ // shortest distances
62+ vector<int >distances (n, INT_MAX);
63+ distances[src] =0 ;
64+ // shortest steps
65+ vector<int >currStops (n, INT_MAX);
66+ currStops[src] =0 ;
67+
68+ // priority queue -> (cost, node, stops)
69+ priority_queue<vector<int >, vector<vector<int >>, greater<vector<int >>> pq;
70+ pq.push ({0 , src,0 });
71+
72+ while (!pq.empty ()) {
73+ int cost = pq.top ()[0 ];
74+ int node = pq.top ()[1 ];
75+ int stops = pq.top ()[2 ];
76+ pq.pop ();
77+
78+ // if destination is reached, return cost to get here
79+ if (node == dst) {
80+ return cost;
81+ }
82+
83+ // if no more steps left, continue
84+ if (stops == k +1 ) {
85+ continue ;
86+ }
87+
88+ // check & relax all neighboring edges
89+ for (int neighbor =0 ; neighbor < n; neighbor++) {
90+ if (adj[node][neighbor] >0 ) {
91+ int currCost = cost;
92+ int neighborDist = distances[neighbor];
93+ int neighborWeight = adj[node][neighbor];
94+
95+ // check if better cost
96+ int currDist = currCost + neighborWeight;
97+ if (currDist < neighborDist || stops +1 < currStops[neighbor]) {
98+ pq.push ({currDist, neighbor, stops +1 });
99+ distances[neighbor] = currDist;
100+ currStops[neighbor] = stops;
101+ }else if (stops < currStops[neighbor]) {
102+ // check if better steps
103+ pq.push ({currDist, neighbor, stops +1 });
104+ }
105+ currStops[neighbor] = stops;
106+ }
107+ }
108+ }
109+
110+ if (distances[dst] == INT_MAX) {
111+ return -1 ;
112+ }
113+ return distances[dst];
114+ }
115+ };