This is the 24th day of my participation in the August More Text Challenge

Leetcode -787-K is the cheapest flight in transit

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

There are n cities connected by a number of flights. Flights [I] = [fromi, toi, pricei], indicating that the flights all start from city fromi and arrive at Pricei at price toi.

Now given all the cities and flights, as well as the starting city SRC and the destination DST, your task is to find a route with at most k stops that makes the price from SRC to DST the cheapest, and return to that price. If no such route exists, -1 is printed.

Example 1:

Input: n = 3, edges = [,1,100 [0],,2,100 [1], [0,2,500]] SRC = 0, DST = 2 and k = 1 output: 200Copy the code

Explanation: City flights are shown below

The cheapest price from City 0 to city 2 within transit station 1 is 200, as shown in red in the figure.

Example 2:

Input: n = 3, edges = [,1,100 [0],,2,100 [1], [0,2,500]] SRC = 0, DST = 2 and k = 0 output: 500Copy the code

Explanation: City flights are shown below

The cheapest price from City 0 to City 2 within transit station 0 is 500, as shown in blue.

Tip:

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n – 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi ! = toi
  • 1 <= pricei <= 10⁴
  • There was no duplication of flights and there was no self-loop
  • 0 <= src, dst, k < n
  • src ! = dst

Related Topics

  • Depth-first search
  • Breadth-first search
  • figure
  • Dynamic programming
  • The short circuit
  • Heap (Priority queue)
  • 👍 👎 0 307

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: DFS+ violence

  • Keep iterating from the SRC node
  • Record the number of traversal layers
  • Map is also used to store the element set corresponding to each SRC node to simplify the search
Map<Integer, List<Integer>> map = new HashMap<>();
int des, maxStep, min;
int[][] temp;

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    for (int i = 0; i < flights.length; i++) {
        List<Integer> list = map.getOrDefault(flights[i][0].new ArrayList<>());
        list.add(i);
        map.put(flights[i][0], list);
    }
    des = dst;
    maxStep = k;
    min = Integer.MAX_VALUE;
    temp = flights;
    dfs(src, 0.0);
    return min == Integer.MAX_VALUE ? -1 : min;
}


public void dfs(int src, int step, int price) {
    // Boundary conditions
    if(step > maxStep && src ! = des) {return;
    }
    if (src == des) {
        min = Math.min(price, min);
        return;
    }
    for (int num : map.getOrDefault(src, new ArrayList<>())
    ) {
        dfs(temp[num][1], step + 1, price + temp[num][2]); }}Copy the code
  • Time complexity
    O ( k ∗ n 2 ) O(k*n^2)
  • Spatial complexity
    O ( k ∗ n 2 ) O(k*n^2)

Idea 2: Dynamic planning

  • I don’t know how to write mnemonic DFS, so let’s write DP
  • Define the equation DP. Dp [k][I] represents the minimum cost of reaching node I through k nodes
  • Dp [k][I] = min(f((k-1),j) + price(j, I))
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int INF = 0x3f3f3f3f;
    int[][] dp = new int[k + 2][n];
    for (int i = 0; i < k + 2; ++i) {
        Arrays.fill(dp[i], INF);
    }
    dp[0][src] = 0;
    for (int i = 1; i <= k + 1; i++) {
        for (int[] num : flights
        ) {
            dp[i][num[1]] = Math.min(dp[i - 1][num[0]] + num[2], dp[i][num[1]]); }}int res = INF;
    for (int i = 0; i <= k+1; i++) {
        res = Math.min(res, dp[i][dst]);
    }
    return res ==INF ? -1 : res;
}
Copy the code
  • Time complexity
    O ( k ∗ n 2 ) O(k*n^2)
  • Spatial complexity
    O ( k ∗ n 2 ) O(k*n^2)

Idea 3: Dimensionality reduction

  • The above dp[I] equation only relates to DP [i-1]
  • So you can do dimension reduction
  • Dp [I] represents the minimum cost to point I
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int INF = 0x3f3f3f3f;
    int[] dp = new int[n];

    Arrays.fill(dp, INF);
    dp[src] = 0;

    int res = INF;
    for (int i = 1; i <= k + 1; i++) {
        int[] g = new int[n];
        Arrays.fill(g, INF);
        for (int[] num : flights
        ) {
            g[num[1]] = Math.min(dp[num[0]] + num[2], g[num[1]]);
        }
        dp = g;
        res = Math.min(res, dp[dst]);
    }
    return res == INF ? -1 : res;
}
Copy the code
  • Time complexity
    O ( k ∗ ( n + m ) ) O(k*(n+m))
  • Spatial complexity
    O ( k ∗ ( n + m ) ) O(k*(n+m))

Idea 4: Memorizing DFS

Map<Integer, List<Integer>> map = new HashMap<>(); int des; int[][] temp; int[][] cache; int INF = 0x3f3f3f3f; int res = INF; public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { for (int i = 0; i < flights.length; i++) { List<Integer> list = map.getOrDefault(flights[i][0], new ArrayList<>()); list.add(i); map.put(flights[i][0], list); } des = dst; temp = flights; cache = new int[k + 2][n]; for (int i = 0; i <= k + 1; i++) { for (int j = 0; j < n; j++) { cache[i][j] = j == src ? 0 : INF; } } dfs(src, 0, 0, k); return res == INF ? -1 : res; } public void DFS (int SRC, int step, int price, int k) {if (des == SRC) {res = math.min (res, price); return; } if (k < 0) { return; } for (int num : map.getOrDefault(src, new ArrayList<>()) ) { if (cache[step + 1][temp[num][1]] <= price + temp[num][2]) { continue; } cache[step + 1][temp[num][1]] = price + temp[num][2]; dfs(temp[num][1], step + 1, price + temp[num][2], k - 1); }}Copy the code
  • Time complexity
    O ( k ∗ n 2 ) O(k*n^2)
  • Spatial complexity
    O ( k ∗ n 2 ) O(k*n^2)

Idea 5: BFS algorithm

  • BFS is a better algorithm to understand
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
            Map<Integer, List<Integer>> map = new HashMap<>();
            int INF = 0x3f3f3f3f;
            List<int[]>[] edge = new List[n];
            int[] vis = new int[n];
            for(int i = 0; i < n; ++i){
                edge[i] = new ArrayList<>();
            }
            for (int[] flight : flights) {
                edge[flight[0]].add(new int[]{flight[1], flight[2]});
            }
            Arrays.fill(vis, INF);
            vis[src] = 0;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{src, 0, vis[src]});
            while(! queue.isEmpty()) {int[] poll = queue.poll();
                if (poll[1] > k) break;
                for (int[] next : edge[poll[0]]) {
                    if (vis[next[0]] > poll[2] + next[1]) {
                        vis[next[0]] = poll[2] + next[1];
                        queue.add(new int[]{next[0], poll[1] + 1, vis[next[0]]}); }}}return vis[dst] == INF ? -1 : vis[dst];
        }
Copy the code
  • Time complexity
    O ( k ∗ n 2 ) O(k*n^2)
  • Spatial complexity
    O ( k ∗ n 2 ) O(k*n^2)

Idea six: BF algorithm and its dimension optimization

  • This idea can basically be said to be realized with DP
  • Specific analysis we can refer to the three Leaf big guy’s code
int N = 110, INF = 0x3f3f3f3f;
int[][] g = new int[N][N];
int[] dist = new int[N];
int n, m, s, t, k;
public int findCheapestPrice(int _n, int[][] flights, int _src, int _dst, int _k) {
    n = _n; s = _src; t = _dst; k = _k + 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            g[i][j] = i == j ? 0: INF; }}for (int[] f : flights) {
        g[f[0]][f[1]] = f[2];
    }
    int ans = bf();
    return ans > INF / 2 ? -1 : ans;
}
int bf(a) {
    Arrays.fill(dist, INF);
    dist[s] = 0;
    for (int limit = 0; limit < k; limit++) {
        // This step is crucial
        int[] clone = dist.clone();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) { dist[j] = Math.min(dist[j], clone[i] + g[i][j]); }}}return dist[t];
}
Copy the code
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int N = 110, INF = 0x3f3f3f3f;
    // Initialize the shortest path to the current node
    int[] vis = new int[N];
    Arrays.fill(vis, INF);
    vis[src] = 0;
    for (int i = 0; i < k + 1; i++) {
        int[] g = vis.clone();
        for (int[] f: flights
             ) {
            int x = f[0], y = f[1], w = f[2]; vis[y] = Math.min(vis[y], g[x] + w); }}return vis[dst] > INF / 2 ? -1 : vis[dst];
}
Copy the code
  • Time complexity
    O ( k ∗ ( n + m ) ) O(k*(n+m))
  • Spatial complexity
    O ( k ∗ ( n + m ) ) O(k*(n+m))