#195HardGraphs· Bounded-Edge Shortest Path

Cheapest Route With a Stop Limit

An airline sells connecting tickets over `n` cities numbered `0` to `n - 1`. Each one-way flight is `[from, to, price]`. A traveller wants to go from city `src` to city `dst` using at most `stops` intermediate cities (so at most `stops + 1` flights in total) and paying as little as possible. Return the cheapest total price of such a trip, or `-1` if no trip with at most `stops` intermediate cities exists. Note that the cheapest route overall may use too many stops and therefore not be allowed.

Input format

`n`: number of cities; `flights`: an array of triples `[from, to, price]`; `src`, `dst`: the start and destination; `stops`: the maximum number of intermediate cities.

Output format

An integer: the minimum price of a trip with at most `stops` intermediate cities, or -1.

Examples

Input: n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], src = 0, dst = 3, stops = 1

Output: 700

With one stop the best route is 0 -> 1 -> 3 for 700. The cheaper 0 -> 1 -> 2 -> 3 costs 400 but uses two stops.

Input: n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], src = 0, dst = 3, stops = 2

Output: 400

With two stops the route 0 -> 1 -> 2 -> 3 for 400 becomes allowed.

Input: n = 3, flights = [[0, 1, 100], [1, 2, 100]], src = 0, dst = 2, stops = 0

Output: -1

Without stops only a direct flight is allowed, and none exists: -1.

Constraints

2 <= n <= 100
0 <= flights.length <= n * (n - 1)
0 <= from, to < n and from != to; each ordered pair appears at most once
1 <= price <= 10^4
0 <= src, dst, stops < n and src != dst

Study first

Shortest Paths: Dijkstra and Bellman-Ford

#graph
#shortest-path
#bellman-ford
#dynamic-programming