Поиск кратчайшего пути с ограничениями. Найти первые K коротких путей.
Difference between ru2 and ru3, changed 2 character(s)
Здравствуйте! ↵
Условие задачи: Имеется N автовокзалов из которых ходят автобусы. Для каждого автобуса известны стоимость достижения до других автовокзалов, даты когда автобус уезжает в другой автовокзал и когда автобус туда приезжает. На вход подаются два города (начальный и конечный), а также дата когда мы хотим отправиться. Нужно вывести первые K самых дешёвых маршрутов,  а также первые K самых быстрых.↵
↵
Как найти первыйе K самых дешёвых маршрутов?↵
↵
Насколько я понимаю эта задача решается перебором и алгоритм Дейкстры тут неприменим. Как можно написать перебор более менее оптимально? За какую асимптотику?↵
Спасибо!↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian tamirOK 2016-07-18 17:04:38 2 Мелкая правка: 'айти первый K самых д' -> 'айти первые K самых д'
ru2 Russian tamirOK 2016-07-18 17:04:01 8 Мелкая правка: 'ия до другого автовокзала, даты ког' -> 'ия до других автовокзалов, даты ког'
ru1 Russian tamirOK 2016-07-18 17:03:26 700 Первая редакция (опубликовано)