💡 Задача: Самые дешевые авиабилеты в пределах K остановок

Условие: Имеется n городов, соединенных некоторым количеством рейсов. Вам дан массив flights, где flights[i] = [fromi, toi, pricei] означает, что существует рейс из города fromi в город toi со стоимостью pricei.

Также даны три целых числа src, dst и k, возвращаем самую дешевую цену из src в dst с не более чем k остановками. Если такого маршрута не существует, возвращается -1.

Пример:

Ввод: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Вывод: 700

Ввод: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Вывод: 200

📌Решение

Пишите свое решение в комментариях👇

@python_job_interview