Standard Bar Graphs · Shortest Path Problems O((n + E) * k) · O(n)
A regional courier quotes one-way legs between cities, but a freight pass caps how many intermediate cities a discounted run may touch. The pricing desk must quote the cheapest legal total from the origin depot to the destination — where 'legal' means at most k intermediate stops — or declare the pair unservable under the cap.
Input: An integer n (cities 0..n-1), a flight list flights where [u, v, w] is a one-way leg u -> v costing w, plus src, dst, and the stop cap k.
Output: Return the cheapest total cost from src to dst using at most k intermediate stops, or -1 if no such route exists.
1 <= n <= 1000 <= k < n1 <= flights.length <= 10^40 <= w <= 10^4No duplicate or self-route legsInput: {"n":4,"flights":[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],"src":0,"dst":3,"k":1}
Output: 700
The 100+200 steal needs two stops and is illegal; the best one-stop route is 100 + 600 = 700.
Input: {"n":3,"flights":[[0,1,100],[1,2,100],[0,2,500]],"src":0,"dst":2,"k":0}
Output: 500
With zero stops allowed, only the direct 500 leg qualifies.