Ответ:
Маршруты 1, 3 и 6 охватывают все четыре объекта: маршрут 1 — Русский музей, маршрут 3 — Петропавловская крепость, маршрут 6 — Исаакиевский собор и Эрмитаж. Их стоимость: 300 + 450 + 1400 = 2150 руб.
Для проверки минимальности: Петропавловская крепость есть только в маршрутах 3 и 4; Русский музей — только в маршрутах 1 и 2. Если взять маршрут 4 вместо маршрута 3, Эрмитаж уже включён, но нужно отдельно посетить Исаакиевский собор (маршрут 2 или 6), и стоимость будет не меньше 1400 + 300 + 1400 = 3100 руб. При маршруте 3 дешевле всего добавить маршрут 1 для Русского музея и маршрут 6 для Исаакиевского собора и Эрмитажа: всего 2150 руб.
Ответ: 136
Маршруты 1, 3 и 6 охватывают все четыре объекта: маршрут 1 — Русский музей, маршрут 3 — Петропавловская крепость, маршрут 6 — Исаакиевский собор и Эрмитаж. Их стоимость: 300 + 450 + 1400 = 2150 руб.
Для проверки минимальности: Петропавловская крепость есть только в маршрутах 3 и 4; Русский музей — только в маршрутах 1 и 2. Если взять маршрут 4 вместо маршрута 3, Эрмитаж уже включён, но нужно отдельно посетить Исаакиевский собор (маршрут 2 или 6), и стоимость будет не меньше 1400 + 300 + 1400 = 3100 руб. При маршруте 3 дешевле всего добавить маршрут 1 для Русского музея и маршрут 6 для Исаакиевского собора и Эрмитажа: всего 2150 руб.
Ответ: 136
