Задача №07976

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

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

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

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

Заметим, что Петропавловская крепость представлена только в маршрутах 4 и 6. Рассмотрим варианты, начиная с них:

1. Выберем маршрут 4 (П, И). Его стоимость составляет $1300\text{ руб.}\text{.}$

• Осталось посетить Э и Р.
• Вариант А: маршрут 1 (Э) и маршрут 5 (Р). Итоговая стоимость: $1300+300+350=1950\text{ руб.}$ (набор 1, 4, 5).
• Вариант Б: маршрут 2 (Э, Р). Итоговая стоимость: $1300+1450=2750\text{ руб.}$ (набор 2, 4).

2. Выберем маршрут 6 (П, Р). Его стоимость составляет $1600\text{ руб.}\text{.}$

• Осталось посетить Э и И.
• Вариант А: маршрут 1 (Э) и маршрут 3 (И). Итоговая стоимость: $1600+300+350=2250\text{ руб.}$ (набор 1, 3, 6).
• Вариант Б: маршрут 1 (Э) и маршрут 4 (П, И). В этом случае Петропавловская крепость уже посещена (маршрут 6), поэтому такой набор будет избыточным и более дорогим.

3. Другие комбинации: без использования маршрутов 4 или 6 невозможно посетить Петропавловскую крепость.

Сравним общие стоимости:

• маршруты 1, 4, 5: $1950\text{ руб.}\text{;}$
• маршруты 2, 4: $2750\text{ руб.}\text{;}$
• маршруты 1, 3, 6: $2250\text{ руб.}\text{.}$

Наименьшая сумма составляет $1950\text{ руб.}$ при выборе маршрутов 1, 4 и 5.

Ответ: 145