There are
n
cities connected bym
flights. Each flight starts from cityu
and arrives atv
with a pricew
.Now given all the cities and flights, together with starting city
src
and the destinationdst
, your task is to find the cheapest price fromsrc
todst
with up tok
stops. If there is no such route, output-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:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
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:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
- The number of nodes
n
will be in range[1, 100]
, with nodes labeled from0
ton - 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.
- mine
- Java
- DFS
Runtime: 97 ms, faster than 6.45%, Memory Usage: 40.1 MB, less than 67.44% of Java online submissions
// O(?)time O(E)space // E = flights.length // if each city has two flights, time complexity will be 2^K int res = Integer.MAX_VALUE; public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { Map<Integer, List<int[]>> map = new HashMap<>(); for (int[] flight : flights) { List<int[]> next = map.getOrDefault(flight[0], new ArrayList<>()); next.add(flight); map.put(flight[0], next); } dfs(map, src, dst, K, 0); return res == Integer.MAX_VALUE ? -1 : res; } public void dfs(Map<Integer, List<int[]>> map, int src, int dst, int K, int count) { if (K < 0) { return; } List<int[]> next = map.getOrDefault(src, new ArrayList<>()); if (next.size() == 0) { return; } for (int i = 0; i < next.size(); i++) { int p = count + next.get(i)[2]; if (p > res) { continue; } if (next.get(i)[1] == dst) { res = Math.min(p, res); continue; } dfs(map, next.get(i)[1], dst, K - 1, p); } }
- DFS
- Java
-
the most votes
-
Priority Queue
Runtime: 14 ms, faster than 36.17%, Memory Usage: 41.5 MB, less than 42.53% of Java online submissions
// O(E)time O(N)space // E = flights.length public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { Map<Integer, Map<Integer, Integer>> prices = new HashMap<>(); for (int[] f : flights) { if (!prices.containsKey(f[0])) prices.put(f[0], new HashMap<>()); prices.get(f[0]).put(f[1], f[2]); } Queue<int[]> pq = new PriorityQueue<>((a, b) -> (Integer.compare(a[0], b[0]))); pq.add(new int[]{0, src, k + 1}); while (!pq.isEmpty()) { int[] top = pq.remove(); int price = top[0]; int city = top[1]; int stops = top[2]; if (city == dst) return price; if (stops > 0) { Map<Integer, Integer> adj = prices.getOrDefault(city, new HashMap<>()); for (int a : adj.keySet()) { pq.add(new int[]{price + adj.get(a), a, stops - 1}); } } } return -1; }
-
Dynamic Programming
Runtime: 5 ms, faster than 82.88%, Memory Usage: 40 MB, less than 68.32% of Java online submission
// O(E)time O(E)space // E = flight.length class Edge { int v, w; public Edge(int v, int w) { this.v = v; this.w = w; } } public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { List<Edge>[] edges = new ArrayList[n]; for (int i = 0; i < n; i++) { edges[i] = new ArrayList<>(); } for (int i = 0; i < flights.length; i++) { int[] flight = flights[i]; edges[flight[0]].add(new Edge(flight[1], flight[2])); } return findCheapestPrice(edges, src, dst, K + 1, new Integer[n][K + 2]); } public int findCheapestPrice(List<Edge>[] edges, int src, int dst, int k, Integer[][] memo) { if (k < 0) return -1; if (src == dst) return 0; if (memo[src][k] == null) { int min = Integer.MAX_VALUE; for (Edge nei : edges[src]) { int res = findCheapestPrice(edges, nei.v, dst, k - 1, memo); if (res != -1) { min = Math.min(min, res + nei.w); } } if (min == Integer.MAX_VALUE) memo[src][k] = -1; else memo[src][k] = min; } return memo[src][k]; }
-
- the leetcode solution
-
Runtime: 5 ms, faster than 82.88%, Memory Usage: 40 MB, less than 68.32% of Java online submission
// O(E * K)time O(N)space // E = flights.length public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { int[][] dist = new int[2][n]; int INF = Integer.MAX_VALUE / 2; Arrays.fill(dist[0], INF); Arrays.fill(dist[1], INF); dist[0][src] = dist[1][src] = 0; for (int i = 0; i <= K; ++i) for (int[] edge: flights) dist[i&1][edge[1]] = Math.min(dist[i&1][edge[1]], dist[~i&1][edge[0]] + edge[2]); return dist[K&1][dst] < INF ? dist[K&1][dst] : -1; }
-
Dijkstra
Runtime: 11 ms, faster than 51.80%, Memory Usage: 43.8 MB, less than 10.71% of Java online submissions
// O(E + N * logN)time O(N)space // E = flights.length public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { int[][] graph = new int[n][n]; for (int[] flight: flights) graph[flight[0]][flight[1]] = flight[2]; Map<Integer, Integer> best = new HashMap(); PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]); pq.offer(new int[]{0, 0, src}); while (!pq.isEmpty()) { int[] info = pq.poll(); int cost = info[0], k = info[1], place = info[2]; if (k > K+1 || cost > best.getOrDefault(k * 1000 + place, Integer.MAX_VALUE)) continue; if (place == dst) return cost; for (int nei = 0; nei < n; ++nei) if (graph[place][nei] > 0) { int newcost = cost + graph[place][nei]; if (newcost < best.getOrDefault((k+1) * 1000 + nei, Integer.MAX_VALUE)) { pq.offer(new int[]{newcost, k+1, nei}); best.put((k+1) * 1000 + nei, newcost); } } } return -1; }
-