There arencities connected by mflights. Each fight starts from city uand arrives at vwith a pricew.
Now given all the cities and flights, together with starting citysrcand the destination dst, your task is to find the cheapest price fromsrctodstwith up tokstops. If there is no such route, output-1.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output:
200
Explanation:
The graph looks like this:
0
/ \
100 500
/ \
1 ---100--- 2
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output:
500
Explanation:
The graph looks like this:
0
/ \
100 500
/ \
1 ---100--- 2
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked red in the picture.
Note:
The number of nodes nwill be in range[1, 100], with nodes labeled from0ton - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.
Solution
Dijkstra's Algorithm (BFS) with PriorityQueue Implementation
Some explanation.
The key difference with the classic Dijkstra algo is, we don't maintain the global optimal distance to each node, i.e. ignore below optimization:
alt ← dist[u] + length(u, v)
if alt < dist[v]:
Because there could be routes which their length is shorter but pass more stops, and those routes don't necessarily constitute the best route in the end. To deal with this, rather than maintain the optimal routes with 0..K stops for each node, the solution simply put all possible routes into the priority queue, so that all of them has a chance to be processed. IMO, this is the most brilliant part.
And the solution simply returns the first qualified route, it's easy to prove this must be the best route.
Complexity Analysis
Time Complexity: O(E+nlogn), where E is the total number of flights.?
Space Complexity: O(n), the size of the heap.?
class Solution {
class Flight {
int src;
int dst;
int price;
Flight (int src, int dst, int price) {
this.src = src;
this.dst = dst;
this.price = price;
}
}
class Stop {
int id, cost, count;
Stop(int id, int cost, int count) {
this.id = id;
this.cost = cost;
this.count = count;
}
}
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
HashMap<Integer, ArrayList<Flight>> map = new HashMap<>();
for (int[] flight: flights) {
if (!map.containsKey(flight[0])) {
map.put(flight[0], new ArrayList<Flight>());
}
map.get(flight[0]).add(new Flight(flight[0], flight[1], flight[2]));
}
Comparator<Stop> cmp = new Comparator<Stop>() {
public int compare(Stop s1, Stop s2) {
return s1.cost - s2.cost;
}
};
PriorityQueue<Stop> q = new PriorityQueue<Stop>(cmp);
q.offer(new Stop(src, 0, K));
while (q != null && !q.isEmpty()) {
Stop cur = q.poll();
if (cur.id == dst) {
return cur.cost;
}
if (cur.count >= 0) {
List<Flight> list = map.get(cur.id);
if (list == null) {
continue;
}
for (Flight f: list) {
q.offer(new Stop(f.dst, f.price + cur.cost, cur.count - 1));
}
}
}
return -1;
}
}
DFS with Pruning
k - number of flights
n - number of cities
Time Complexity: O(n ^ (k + 1))
Space Complexity: O(k + 1)
DFS中的剪枝很重要，否则会TLE
class Solution {
class Flight {
int src;
int dst;
int price;
Flight (int src, int dst, int price) {
this.src = src;
this.dst = dst;
this.price = price;
}
}
private static int cheapest;
private static boolean routeFound;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
cheapest = Integer.MAX_VALUE;
routeFound = false;
HashMap<Integer, ArrayList<Flight>> map = new HashMap<>();
for (int[] flight: flights) {
if (!map.containsKey(flight[0])) {
map.put(flight[0], new ArrayList<Flight>());
}
map.get(flight[0]).add(new Flight(flight[0], flight[1], flight[2]));
}
boolean[] visited = new boolean[n];
dfs(map, visited, src, dst, 0, K);
if (!routeFound) {
return -1;
}
return cheapest;
}
private void dfs(HashMap<Integer, ArrayList<Flight>> map, boolean[] visited, int src, int dst, int cost, int k) {
if (src == dst) {
routeFound = true;
cheapest = Math.min(cheapest, cost);
return;
}
if (k < 0) {
return;
}
ArrayList<Flight> flights = map.get(src);
if (flights != null) {
for (Flight flight: flights) {
// do not visit same city twice
if (visited[flight.dst]) {
continue;
}
// Pruning: important to reduce computation
if (flight.price + cost > cheapest) {
continue;
}
visited[flight.dst] = true;
dfs(map, visited, flight.dst, dst, cost + flight.price, k - 1);
visited[flight.dst] = false;
}
}
}
}
// build map for adjacency list: (u -> (v1[w1], v2[w2]))
// u -> v : w
// DFS
// k : remaining stops
// src: current src
// dst: final dst
// if k < 0 return
// if src reach dst, update global min with current cost
// when all returned, return the global min