This is the 24th day of my participation in the August More Text Challenge
The cheapest flight within the 787.K stop connection
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.
Your task is to find the cheapest route from SRC to DST through k at most, and return that price. Now given all cities and flights, as well as the departure city SRC and destination DST, the output is -1 if no such route exists.
Example 1:
Edges Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] SRC = 0, DST = 2, k = 1 Output: 200 Interpretation: The city flight diagram is shown belowCopy the code
The cheapest price from City 0 to city 2 within transit station 1 is 200, as shown in red in the figure.Copy the code
Example 2:
Edges input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] SRC = 0, DST = 2, k = 0 output: 500 interpretation: the city flight diagram is shown belowCopy the code
The cheapest price from City 0 to City 2 within transit station 0 is 500, as shown in blue.Copy the code
Tip:
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= fromi, toi < n
fromi ! = toi
1 <= pricei <= 104
- There was no duplication of flights and there was no self-loop
0 <= src, dst, k < n
src ! = dst
Methods a
Template question: Bellman-Ford algorithm
Bellman-ford algorithm: To find the shortest distance from the starting point SRC to the end point DST in a graph through at most several edges;
- Initialization, first will start the distance
d[src]=0
, set to 0; - It starts at the beginning and spreads out
k
side - Try to update
k
Sub, which is the loopk
time - Where, before updating the distance, each loop copies the array of the distance before the update
tmp
; - I’m going to go through every edge, if
tmp[from] + price < d[to]
Note Can be updatedd[to]
The distance; - Why use it
tmp
Because withtmp
You can avoid updating distances in this updated[to]
To update the other points
class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { int[] d = new int[n]; for (int i = 0; i < n; i ++ ) d[i] = 0x3f3f3f3f; d[src] = 0; for (int i = 0; i <= k; i ++ ) { int[] tmp = (int[])Arrays.copyOf(d, n); for (int j = 0; j < flights.length; j ++ ) { int from = flights[j][0], to = flights[j][1], price = flights[j][2]; d[to] = Math.min(d[to], tmp[from] + price); } } if (d[dst] == 0x3f3f3f3f) return -1; return d[dst]; }}Copy the code