ALG-H009HardGraphs
Cheapest Route with Stop Limit
For directed flights [from,to,cost], find the least total cost from source to destination using at most max_stops intermediate cities (thus at most max_stops+1 edges). Return -1 if impossible.
Contract
input n: integer
input flights: integer[][]
input source: integer
input destination: integer
input max_stops: integer
return integer
Constraints
- • 0 <= node id < n
- • Flight costs > 0
- • max_stops >= 0
Examples
Example 1
n = 4
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500], [2, 3, 100]]
source = 0
destination = 2
max_stops = 1
→ 200
Example 2
n = 3
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
source = 0
destination = 2
max_stops = 0
→ 500
5 judge tests (2 shown above). Target complexity: O((max_stops+1)*edges).