Условие
Туристу нужно добраться из посёлка А в посёлок Д. В таблице указаны все прямые автобусные рейсы между посёлками и цены билетов; рейсы ходят в обе стороны. Рейс | Цена билета А — Б | 180 руб. А — В | 250 руб. Б — В | 60 руб. Б — Г | 320 руб. В — Г | 150 руб. В — Д | 390 руб. Г — Д | 120 руб. Найдите наименьшую стоимость поездки из А в Д (в рублях).
Подсказка
Выпишите, в какие посёлки можно попасть из А, а потом — откуда можно доехать до Д.
Сложите цены билетов для каждого маршрута и сравните суммы.
Показать ответ
510
Пошаговое решение
- Понимаем, что нужно перебрать маршруты
Прямого рейса А — Д нет, поэтому нужны пересадки. Стоимость маршрута — сумма цен всех билетов на нём. Через один посёлок дважды проезжать нет смысла.
- Выписываем все маршруты из А в Д
А–Б–В–Г–Д: 180+60+150+120=510 руб. А–В–Г–Д: 250+150+120=520 руб. А–Б–Г–Д: 180+320+120=620 руб. А–Б–В–Д: 180+60+390=630 руб. А–В–Д: 250+390=640 руб. А–В–Б–Г–Д: 250+60+320+120=750 руб. А–Б–Г–В–Д: 180+320+150+390=1040 руб.
- Выбираем самый дешёвый
Наименьшая стоимость 510 руб. — маршрут А–Б–В–Г–Д. Маршрут с меньшим числом пересадок здесь дороже.
Ответ: 510