Условие
Туристу нужно добраться из посёлка А в посёлок Д. В таблице указаны все прямые автобусные рейсы между посёлками и цены билетов; рейсы ходят в обе стороны. Рейс | Цена билета А — Б | 90 руб. А — В | 200 руб. Б — Г | 240 руб. В — Г | 70 руб. Б — Д | 420 руб. Г — Д | 160 руб. В — Д | 280 руб. Найдите наименьшую стоимость поездки из А в Д (в рублях).
Подсказка
Выпишите, в какие посёлки можно попасть из А, а потом — откуда можно доехать до Д.
Сложите цены билетов для каждого маршрута и сравните суммы.
Показать ответ
430
Пошаговое решение
- Понимаем, что нужно перебрать маршруты
Прямого рейса А — Д нет, поэтому нужны пересадки. Стоимость маршрута — сумма цен всех билетов на нём. Через один посёлок дважды проезжать нет смысла.
- Выписываем все маршруты из А в Д
А–В–Г–Д: 200+70+160=430 руб. А–В–Д: 200+280=480 руб. А–Б–Г–Д: 90+240+160=490 руб. А–Б–Д: 90+420=510 руб. А–Б–Г–В–Д: 90+240+70+280=680 руб. А–В–Г–Б–Д: 200+70+240+420=930 руб.
- Выбираем самый дешёвый
Наименьшая стоимость 430 руб. — маршрут А–В–Г–Д. Маршрут с меньшим числом пересадок здесь дороже.
Ответ: 430