Задача №08173

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

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

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

Заметим, что объект «Эрмитаж» представлен только в маршрутах № 5 и № 6. Рассмотрим варианты, включающие эти маршруты:

1. Если выбран маршрут № 5 (Эрмитаж, Русский музей) за $1600$ руб.:
Для завершения набора необходимо посетить Петропавловскую крепость и Исаакиевский собор.

• Петропавловская крепость представлена в маршрутах № 1 ($350$ руб.) и № 6 (уже содержит Эрмитаж, но стоит $1350$ руб.). Выгоднее взять № 1.
• Исаакиевский собор представлен в маршрутах № 2 ($450$ руб.) и № 3 ($1500$ руб.). Выгоднее взять № 2.

Итоговая стоимость набора (1, 2, 5) составит:
$1600+350+450=2400$ руб.

2. Если выбран маршрут № 6 (Эрмитаж, Петропавловская крепость) за $1350$ руб.:
Для завершения набора необходимо посетить Русский музей и Исаакиевский собор.

• Вариант А: маршрут № 4 (Русский музей, $650$ руб.) + маршрут № 2 (Исаакиевский собор, $450$ руб.). Стоимость:
  $1350+650+450=2450$ руб.
• Вариант Б: маршрут № 3 (Исаакиевский собор, Русский музей, $1500$ руб.). Стоимость:
  $1350+1500=2850$ руб.

Сравним полученные варианты:

• Маршруты 1, 2, 5: $2400$ руб.
• Маршруты 2, 4, 6: $2450$ руб.
• Маршруты 3, 6: $2850$ руб.

Наименьшая сумма составляет $2400$ рублей. Для этого нужно выбрать маршруты под номерами 1, 2 и 5.

Ответ: 125