Здравствуйте! Условие задачи: Имеется N автовокзалов из которых ходят автобусы. Для каждого автобуса известны стоимость достижения до других автовокзалов, даты когда автобус уезжает в другой автовокзал и когда автобус туда приезжает. На вход подаются два города (начальный и конечный), а также дата когда мы хотим отправиться. Нужно вывести первые K самых дешёвых маршрутов, а также первые K самых быстрых.

Как найти первый K самых дешёвых маршрутов?

Насколько я понимаю эта задача решается перебором и алгоритм Дейкстры тут неприменим. Как можно написать перебор более менее оптимально? За какую асимптотику? Спасибо!