| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Кратчайший путь с пересадками |
| Автор: AIs 26.12.2008, 11:34 |
| В городе расположены n автобусных остановок, обозначенных числами из N={1,2,....,n}. Имеется R автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении: М1={I11,I12,...,I1m1}, М2={I21,I22,...,I2m2}, ..... Mr={Ir1,Ir2,...,Irmr}, где Ijk натуральное. Программа должна по заданным номерам остановок I и J определять наиболее быстрый путь перемещения пассажира из остановки I в остановку J с использованием имеющихся маршрутов автобусов при условии, что время движения между соседними остановками у всех маршрутов одинаково и в 3 раза меньше времени изменения маршрута. Кроме того, автобусы могут двигаться в обоих направлениях. В общем, единственная проблема - как обозначить пересадку. |
| Автор: Akina 26.12.2008, 12:42 | ||
Очень просто - остановку X, на которой останавливаются автобусы M и N, раздели на две остановки XM и XN. После того, как ты проделаешь это со всеми остановками и маршрутами, тебя вообще перестанет волновать маршрут. То есть сначала ты разделяешь остановки. Потом для каждой пары начальной Xi и конечной Yi находишь минимум времени движения, после чего из них из всех выбираешь минимальный. |
| Автор: deshton 4.1.2009, 19:46 |
| Никогда не любил задачки подобного плана, я пас. |
