Задача 12 Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Решение:

Задача заключается в поиске кратчайшего пути от точки И до точки М и определении самой длинной дороги на этом пути. Для решения будем использовать алгоритм Дейкстры или аналогичный метод поиска кратчайшего пути.

Таблица расстояний:

Поиск кратчайших путей от И:

• К И: 0
• К А: И → А = 1. Путь: И-А.
• К Б: нет прямого пути из И, кратчайший через А: И-А-Б = 1 + 1 = 2. Путь: И-А-Б.
• К В: И → В = 1. Путь: И-В.
• К Г: нет прямого пути из И.
• К М: И → М = 8. Путь: И-М.
• К Б (альтернативный): И-В-Б = 1 + 2 = 3 (длиннее, чем И-А-Б).
• К А (альтернативный): И-В-А = 1 + 1 = 2 (длиннее, чем И-А).
• К Г: И-В-Б-Г = 1 + 2 + 2 = 5. (через Б). И-А-Б-Г = 1 + 1 + 2 = 4. Путь: И-А-Б-Г.
• К М (альтернативный): И-А-Б-М = 1 + 1 + 3 = 5. И-В-Б-М = 1 + 2 + 3 = 6. И-В-Г-М = 1 + 6 + 1 = 8. И-А-Б-Г-М = 1 + 1 + 2 + 1 = 5. Путь: И-А-Б-М или И-А-Б-Г-М.

Кратчайшие пути от И до М:

• Путь 1: И → А → Б → М. Длина: 1 + 1 + 3 = 5. Участки: И-А (1), А-Б (1), Б-М (3). Максимальная длина участка: 3.
• Путь 2: И → А → Б → Г → М. Длина: 1 + 1 + 2 + 1 = 5. Участки: И-А (1), А-Б (1), Б-Г (2), Г-М (1). Максимальная длина участка: 2.
• Путь 3: И → В → Б → М. Длина: 1 + 2 + 3 = 6. Участки: И-В (1), В-Б (2), Б-М (3). Максимальная длина участка: 3.
• Путь 4: И → В → Б → Г → М. Длина: 1 + 2 + 2 + 1 = 6. Участки: И-В (1), В-Б (2), Б-Г (2), Г-М (1). Максимальная длина участка: 2.
• Путь 5: И → В → Г → М. Длина: 1 + 6 + 1 = 8. Участки: И-В (1), В-Г (6), Г-М (1). Максимальная длина участка: 6.
• Путь 6: И → М. Длина: 8. Участок: И-М (8). Максимальная длина участка: 8.

Сравнивая длины всех кратчайших путей (5, 6, 8), мы видим, что кратчайшие пути имеют длину 5 (Путь 1 и Путь 2).

Теперь рассмотрим эти кратчайшие пути:

• Путь 1: И → А → Б → М (длина 5). Длины участков: И-А (1), А-Б (1), Б-М (3). Самый длинный участок: 3.
• Путь 2: И → А → Б → Г → М (длина 5). Длины участков: И-А (1), А-Б (1), Б-Г (2), Г-М (1). Самый длинный участок: 2.

Сравнивая максимальные длины участков на этих двух кратчайших путях (3 и 2), мы видим, что самый длинный участок среди всех кратчайших путей равен 3.

Финальная проверка:

Рассмотрим все пути от И до М и их максимальные участки:

• И-А-Б-М: 1, 1, 3. Макс: 3. Длина: 5.
• И-А-Б-Г-М: 1, 1, 2, 1. Макс: 2. Длина: 5.
• И-В-Б-М: 1, 2, 3. Макс: 3. Длина: 6.
• И-В-Б-Г-М: 1, 2, 2, 1. Макс: 2. Длина: 6.
• И-В-Г-М: 1, 6, 1. Макс: 6. Длина: 8.
• И-М: 8. Макс: 8. Длина: 8.

Кратчайшие пути имеют длину 5. Среди этих кратчайших путей, самый длинный участок дороги — это участок Б-М длиной 3 (в пути И-А-Б-М).

Ответ: 3