Cheapest Flights Within K Stops
There are n
cities connected by m
flights. Each flight starts from city u
and arrives at v
with a price w
.
Now given all the cities and flights, together with starting city src
and the destination dst
, your task is to find the cheapest price from src
to dst
with up to k
stops. If there is no such route, output -1
.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
Constraints:
The number of nodes
n
will be in range[1, 100]
, with nodes labeled from0
ton - 1
.The size of
flights
will be in range[0, n * (n - 1) / 2]
.The format of each flight will be
(src, dst, price)
.The price of each flight will be in the range
[1, 10000]
.k
is in the range of[0, n - 1]
.There will not be any duplicated flights or self cycles.
Last updated