LeetCode brush topic series - 787 K station transfer within the cheapest flight

There are n cities connected by some flights.You are given an array flights , where flights[i] = [fromi, toi, pricei] , which means that the flights all start from city fromi and arrive at toi at price pricei .

Now given all the cities and flights, as well as the departure city src and the destination dst, your task is to find a route with at most k stops to make the cheapest price from src to dst, and return that price.If no such route exists, 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 city flight map is as follows

The cheapest price from city 0 to city 2 within 1 stop is 200, as shown in 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 city flight map is as follows

The cheapest price from city 0 to city 2 within 0 stops is 500, 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 <= 104
No duplicate flights and no self-loops
0 <= src, dst, k < n
src != dst

Source: LeetCode
Link: https://leetcode.cn/problems/cheapest-flights-within-k-stops

Ideas: Refer to what the Great God wrote: Tourism Saving Money: Weighted Shortest Path :: labuladong's algorithm cheat sheet

If you want to find the city with the least dst cost, then find the city near it

java code:

class Solution {public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {// Define map, key is a node in the graph, value is (in-degree node, weight value)// to -> (from, price)Map> map = new HashMap<>();for (int[] dists : flights) {int from = dists[0];int to = dists[1];int price = dists[2];int[] subValue = {from, price};if (!map.containsKey(to)) {List inValues ​​= new LinkedList<>();inValues.add(subValue);map.put(to, inValues);} else {map.get(to).add(subValue);}}// record table, record the minimum cost from src to memp[i][j] and the number of transfers is jint[][] memp = new int[n][k + 1];for (int[] value : memp) {Arrays.fill(value, -888);}return dp(src, dst, k+1, map, memp);}int dp(int src, int dst, int k, Map> map, int[][] memp) {if (dst == src) {return 0;}if (k == 0) {return -1;}int res = Integer.MAX_VALUE;// when dst has in-degree nodesif (map.containsKey(dst)) {for (int[] subValues ​​: map.get(dst)) {int from = subValues[0];int price = subValues[1];int fromValue = memp[from][k - 1];if (fromValue == -888) {fromValue = dp(src, from, k - 1, map, memp);memp[from][k - 1] = fromValue;}if (fromValue != -1) {res = Math.min(res, price + fromValue);}}}return res == Integer.MAX_VALUE ? -1 : res;}}