Условие
Туристу нужно добраться из посёлка А в посёлок Д. В таблице указаны все прямые автобусные рейсы между посёлками и цены билетов; рейсы ходят в обе стороны. Рейс | Цена билета А — Б | 140 руб. А — Г | 310 руб. Б — В | 190 руб. Б — Г | 130 руб. В — Д | 110 руб. Г — Д | 260 руб. А — Д | 520 руб. Найдите наименьшую стоимость поездки из А в Д (в рублях).
Подсказка
Выпишите, в какие посёлки можно попасть из А, а потом — откуда можно доехать до Д.
Сложите цены билетов для каждого маршрута и сравните суммы.
Показать ответ
440
Пошаговое решение
- Понимаем, что нужно перебрать маршруты
Есть прямой рейс, но с пересадками может получиться дешевле. Стоимость маршрута — сумма цен всех билетов на нём. Через один посёлок дважды проезжать нет смысла.
- Выписываем все маршруты из А в Д
А–Б–В–Д: 140+190+110=440 руб. А–Д: прямой рейс, 520 руб. А–Б–Г–Д: 140+130+260=530 руб. А–Г–Д: 310+260=570 руб. А–Г–Б–В–Д: 310+130+190+110=740 руб.
- Выбираем самый дешёвый
Наименьшая стоимость 440 руб. — маршрут А–Б–В–Д. Маршрут с меньшим числом пересадок здесь дороже.
Ответ: 440