Задача №08051

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

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

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

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

Рассмотрим возможные варианты:
1. Покрытие объекта П: отдельный маршрут 4 стоит $350\text{ руб.}\text{,}$ маршрут 2 (П + Э) стоит $1450\text{ руб.}\text{.}$
2. Покрытие объекта Р: отдельный маршрут 6 стоит $350\text{ руб.}\text{,}$ маршрут 3 (Р + И) стоит $1400\text{ руб.}\text{.}$
3. Покрытие объекта Э: отдельный маршрут 5 стоит $400\text{ руб.}\text{,}$ маршрут 1 (Э + И) — $1600\text{ руб.}\text{,}$ маршрут 2 (Э + П) — $1450\text{ руб.}\text{.}$
4. Покрытие объекта И: только в комбинациях — маршрут 1 (И + Э) или маршрут 3 (И + Р).

Попробуем минимизировать стоимость:

• Покрываем П самым дешёвым способом — маршрутом 4 за $350\text{ руб.}\text{.}$
• Остаются И, Р, Э. Покрываем И и Р комбинированным маршрутом 3 за $1400\text{ руб.}$ (это дешевле, чем брать отдельно И и Р, так как отдельного маршрута на И нет).
• Остаётся Э — берём маршрут 5 за $400\text{ руб.}\text{.}$

Итоговый набор: маршруты 3, 4, 5. Объекты: маршрут 3 даёт И и Р, маршрут 4 даёт П, маршрут 5 даёт Э. Все четыре музея покрыты.

Вычислим стоимость:

$$1400+350+400=2150\text{ руб.}$$

Проверим другие варианты:

• Набор (1, 4, 6): $1600+350+350=2300\text{ руб.}\text{,}$ дороже.
• Набор (2, 3): $1450+1400=2850\text{ руб.}\text{,}$ дороже.
• Набор (3, 4, 6): $1400+350+350=2100\text{ руб.}\text{,}$ но не хватает Э.
• Набор (1, 4, 5): $1600+350+400=2350\text{ руб.}\text{,}$ не хватает Р.
• Любые наборы из четырёх и более маршрутов будут стоить ещё дороже.

Таким образом, минимальная сумма $2150\text{ руб.}$ достигается при выборе маршрутов 3, 4, 5.

Ответ: 345