There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return-1.
Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
Constraints:
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi != toi
1 <= pricei <= 104
There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst
Accepted421.1KSubmissions1.1MAcceptance Rate37.3%
Intuition
Approach:
// Cannot do based on distance, as Some path with more stops can reach
// node with less weight, but someone with more weight and stops will not reach
// eg 5
// 1 --- 2
// \ / \ 1
// 2 \ / 1 \
// 3 4
// Look here If we want to reach 4, Min disatce with diskstra is 4
// But with less stops we can reach the 4 taking 6
// Hence we priorotize on stops, rather than distance
Links
Video Links
Approach 1:
C++
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
// Stops, node, distance
queue<array<int,3>>q;
vector<int> dist(n, INT_MAX);
vector<vector<vector<int>>> adj(n);
for(auto &it: flights){
int x = it[0], y = it[1], dist = it[2];
adj[x].push_back({y, dist});
}
dist[src] = 0;
q.push({0, src, 0});
while (!q.empty()) {
array<int,3> arr = q.front();
int stp = arr[0], node = arr[1], distance = arr[2];
q.pop();
if(stp > k)
continue;
for(auto &it: adj[node]){
int neigh = it[0], step = it[1];
if(distance + step < dist[neigh] and stp<=k){
dist[neigh] = step + distance;
q.push({stp+1, neigh, dist[neigh]});
}
}
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
};
