Условие: Номер 9

Задача 8. В городе расположены n автобусных остановок, обозначенных числами из N={1,2,....,n}. Имеется R автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении: М1={I11,I12,...,I1m1}, М2={I21,I22,...,I2m2}, ..... Mr={Ir1,Ir2,...,Irmr}, где Ijk натуральное. Написать программу, которая по заданным номерам остановок I и J определяет наиболее быстрый путь перемещения пассажира из остановки I в остановку J с использованием имеющихся маршрутов автобусов при условий, что время движения между соседними остановками у всех маршрутов одинаково и в 3 раза меньше времени изменения маршрута. Кроме того, автобусы могут двигаться в обоих направлениях.

  Решение задачи: Номер 9

Решение задачи 8. Идея решения основывается на использовании очередей. Но если реализация движения от остановки к остановке по одному маршруту аналогична технике, используемой в задаче 6, то возможность изменения маршрутов несколько усложняет структуру элемента в очереди. Для этого для каждой остановки введем тройку чисел (О,М,За), где О - номер остановки, М - номер маршрута, За - величина задержки. При выборе очередного элемента из очереди возможны 2 ситуации. Продолжается движение по тому же маршруту. В этом случае в очередь заносятся тройки типа (О',М,За), где О' - номер остановки, соседней О, в маршруте М, а За=0. 2.Изменяется маршрут. В этом случае в очередь заносятся тройки типа (О,М',За), где М' - номер измененного маршрута, За=3 (задержка на пересадку). При этом новые тройки порождаются только тройками с задержкой, равной 0. В случае тройки с ненулевой задержкой она вновь помещается в очередь с уменьшенным на 1 значением задержки.

Назад