Cheapest Flight with Its Path
Airbnb● HardFULLTIMEOAONSITE INTERVIEWProblem statement
There are n cities numbered from 0 to n - 1. Each flight [from, to, price] is a directed edge with a positive price.
Find a minimum-cost route from src to dst that uses at most k intermediate stops, which is at most k + 1 flights.
Return an integer array whose first element is the total price and whose remaining elements are the visited city sequence from src through dst. If no valid route exists, return [-1].
When several routes have the same minimum price, prefer the route with fewer flights. If a tie remains, prefer the lexicographically smaller city sequence.
Function
cheapestFlightPath(n: int, flights: int[][], src: int, dst: int, k: int) → int[]Examples
Example 1
n = 4flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500],[1,3,600]]src = 0dst = 3k = 2return = [300,0,1,2,3]The route 0 → 1 → 2 → 3 uses three flights, has two intermediate stops, and costs 300.
Example 2
n = 3flights = [[0,1,100],[1,2,100],[0,2,500]]src = 0dst = 2k = 0return = [500,0,2]No intermediate stop is allowed, so only the direct flight is eligible.
Constraints
1 <= n <= 100.0 <= flights.length <= 5000.flights[i].length == 3.0 <= from, to, src, dst < n.from != to, and no two flights have the same ordered endpoint pair.1 <= price <= 10^6.0 <= k < n.- Every valid route price fits in a signed 32-bit integer.