Задача №08138

Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.

Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму?

В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.

Обозначим объекты: Э — Эрмитаж, Р — Русский музей, П — Петропавловская крепость, И — Исаакиевский собор.

Данные маршруты:
1. Э ($300$ руб.)
2. И, Э ($1600$ руб.)
3. П ($450$ руб.)
4. П, Р ($1400$ руб.)
5. Р ($500$ руб.)
6. И, Р ($1400$ руб.)

Нужно покрыть все четыре объекта с минимальной стоимостью.

Заметим, что Исаакиевский собор (И) можно посетить только через маршруты 2 или 6. Рассмотрим эти случаи.

Случай 1: выбираем маршрут 2 (И, Э).

В этом случае уже выбраны объекты И и Э. Остаётся посетить П и Р.

• Для объекта П можно выбрать маршрут 3 ($450$ руб.) или 4 ($1400$ руб., также включает Р).
• Для объекта Р можно выбрать маршрут 5 ($500$ руб.) или 6 ($1400$ руб., также включает И).

Наименьшая стоимость в данном случае достигается при выборе маршрутов 2, 3 и 5:

$$1600+450+500=2550\text{ руб.}$$

Случай 2: выбираем маршрут 6 (И, Р).

В этом случае уже выбраны объекты И и Р. Остаётся посетить Э и П.

• Для объекта Э можно выбрать маршрут 1 ($300$ руб.) или 2 ($1600$ руб., также включает И).
• Для объекта П можно выбрать маршрут 3 ($450$ руб.) или 4 ($1400$ руб., также включает Р).

Наименьшая стоимость в данном случае достигается при выборе маршрутов 6, 1 и 3:

$$1400+300+450=2150\text{ руб.}$$

Сравнивая результаты двух случаев, видим:

$$2150<2550.$$

Другие комбинации (например, с использованием маршрута 4) приведут к стоимости не менее $2150$ руб.

Таким образом, минимальная сумма затрат составляет $2150$ руб. при выборе маршрутов 1, 3 и 6.

Ответ: 136