Graphs
There are
ncities connected by some number of flights. You are given an arrayflightswhereflights[i] = [from[i], to[i], price[i]]indicates that there is a flight from cityfrom[i]to city toi with costprice[i].You are also given three integers
src,dst, andk, return the cheapest price fromsrctodstwith at mostkstops. If there is no such route, return -1.Constraints:
- 1 <= n <= 100`
0 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= from[i], to[i] < nfrom[i] != to[i]1 <= price[i] <= 10**4- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dsthttps://leetcode.com/problems/cheapest-flights-within-k-stops/
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.
Exampoe 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.
The problem asks the shortest path based on an edge weight. Given that, Dijkstra or Bellman Ford might come up as a solution. However, simple breadth first search (BFS) also works. The solution here uses an array to save a total weights of the visited node.
The first step is to create a directed graph with edge weights. The solution here uses a tuple or array of (node, weight). Once the graph is created, do the graph traversal by BFS. The visited state is saved in a queue instead of typical set data structure. This is to handle at most k stops condition. While traversing, if the visited count exceeds the currently visiting node, skip the further process. When the popped out node is the destination, return the weight.
#include <queue>
#include <vector>
using namespace std;
class CheapestFlightsWithinKStops {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int, int>>> graph(n);
for (auto flight: flights) {
int s = flight[0], d = flight[1], w = flight[2];
graph[s].push_back({d, w});
}
vector<int> weights(n, INT_MAX);
weights[src] = 0;
queue<vector<int>> q;
q.push({0, 0, src}); // weight, stops, node
while (!q.empty()) {
vector<int> cur = q.front();
q.pop();
int cur_w = cur[0], cur_s = cur[1], cur_n = cur[2];
if (cur_s > k) { continue; }
for (auto &[next_n, next_w] : graph[cur_n]) {
if (cur_w + next_w < weights[next_n] && cur_s <= k) {
weights[next_n] = cur_w + next_w;
q.push({weights[next_n], cur_s + 1, next_n});
}
}
}
return weights[dst] == INT_MAX ? -1 : weights[dst];
}
};
import java.util.*;
class CheapestFlightsWithinKStops {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<List<Integer>>> graph = new ArrayList<>();
for (int i = 0; i < n; ++i) { graph.add(new ArrayList<>()); }
for (int i = 0; i < flights.length; ++i) {
int s = flights[i][0], d = flights[i][1], w = flights[i][2];
graph.get(s).add(new ArrayList<>(){ {
add(d);
add(w);
} });
}
int[] weights = new int[n];
Arrays.fill(weights, Integer.MAX_VALUE);
weights[src] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0, src});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cur_w = cur[0], cur_s = cur[1], cur_n = cur[2];
if (cur_s > k) { continue; }
List<List<Integer>> adjs = graph.get(cur_n);
for (int i = 0; i < adjs.size(); ++i) {
int next_n = adjs.get(i).get(0), next_w = adjs.get(i).get(1);
if (cur_w + next_w < weights[next_n] && cur_s <= k) {
weights[next_n] = cur_w + next_w;
queue.add(new int[]{weights[next_n], cur_s + 1, next_n});
}
}
}
return weights[dst] == Integer.MAX_VALUE ? -1 : weights[dst];
}
}
/**
* @param {number} n
* @param {number[][]} flights
* @param {number} src
* @param {number} dst
* @param {number} k
* @return {number}
*/
var findCheapestPrice = function(n, flights, src, dst, k) {
const graph = [...Array(n)].map(_ => []);
for (const [s, d, w] of flights) {
graph[s].push([d, w]);
}
const weights = Array(n).fill(Infinity);
weights[src] = 0;
const queue = [[0, 0, src]]; // weight, stops, node
while (queue.length > 0) {
const [cur_w, cur_s, cur_n] = queue.shift();
if (cur_s > k) { continue; }
for (const [next_n, next_w] of graph[cur_n]) {
if ((cur_w + next_w) < weights[next_n] && cur_s <= k) {
weights[next_n] = cur_w + next_w;
queue.push([weights[next_n], cur_s + 1, next_n]);
}
}
}
return weights[dst] === Infinity ? -1 : weights[dst];
};
from typing import List
class CheapestFlightsWithinKStops:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = [[] for _ in range(n)]
for s, d, w in flights:
graph[s].append([d, w])
weights = [float('inf') for _ in range(n)];
weights[src] = 0
queue = [[0, 0, src]]
while queue:
cur_w, cur_s, cur_n = queue.pop(0)
if cur_s > k:
continue
for next_n, next_w in graph[cur_n]:
if cur_w + next_w < weights[next_n] and cur_s <= k:
weights[next_n] = cur_w + next_w
queue.append([weights[next_n], cur_s + 1, next_n])
return -1 if weights[dst] == float('inf') else weights[dst]
# @param {Integer} n
# @param {Integer[][]} flights
# @param {Integer} src
# @param {Integer} dst
# @param {Integer} k
# @return {Integer}
def find_cheapest_price(n, flights, src, dst, k)
graph = Array.new(n){Array.new}
flights.each do |s, d, w|
graph[s] << [d, w]
end
weights = Array.new(n, Float::INFINITY)
weights[src] = 0
queue = [[0, 0, src]]
while !queue.empty?
cur_w, cur_s, cur_n = queue.shift
if cur_s > k
next
end
graph[cur_n].each do |next_n, next_w|
if cur_w + next_w < weights[next_n] && cur_s <= k
weights[next_n] = cur_w + next_w
queue << [weights[next_n], cur_s + 1, next_n]
end
end
end
return weights[dst] == Float::INFINITY ? -1 : weights[dst]
end
O(n + e * k) – n: number of vertices, e: number of edges, k: given kO(n + e)