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 distanced[src]=0, set to 0;
  • It starts at the beginning and spreads outkside
  • Try to updatekSub, which is the loopktime
  • Where, before updating the distance, each loop copies the array of the distance before the updatetmp;
  • I’m going to go through every edge, iftmp[from] + price < d[to]Note Can be updatedd[to]The distance;
  • Why use ittmpBecause withtmpYou 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