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

Question

Вопрос:

Accepted Answer

Определяем кратчайший путь от Ивана-Царевича (И) до Марьи-Царевны (М) с помощью таблицы расстояний.

Ищем пути от И до М:

Кратчайшие пути (по сумме длин участков):

И -> А -> Б -> М: 1 + 1 + 3 = 5
И -> В -> Б -> М: 1 + 2 + 3 = 6
И -> Г -> М: 6 + 8 = 14
И -> А -> М: (нет прямого пути А-М, но есть И-А 1, а также А-Б 1, Б-М 3, итого 1+1+3=5)
И -> В -> М: 1 + 1 = 2
И -> А -> В -> М: 1 + 2 + 1 = 4
И -> В -> Г -> М: 1 + 6 + 8 = 15
И -> А -> В -> Г -> М: 1 + 2 + 6 + 8 = 17

Кратчайший путь: И -> В -> М, длина 2.

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

Анализируем другие пути, чтобы убедиться, что 2 - действительно кратчайший:

И -> А -> Б -> М: 1 + 1 + 3 = 5. Длинный участок: 3.
И -> В -> Б -> М: 1 + 2 + 3 = 6. Длинный участок: 3.
И -> А -> В -> М: 1 + 2 + 1 = 4. Длинный участок: 2.
И -> В -> Г -> М: 1 + 6 + 8 = 15. Длинный участок: 8.
И -> А -> В -> Г -> М: 1 + 2 + 6 + 8 = 17. Длинный участок: 8.
И -> А -> Б -> Г -> М: 1 + 1 + 6 + 8 = 16. Длинный участок: 8.
И -> А -> Б -> В -> М: 1 + 1 + 2 + 1 = 5. Длинный участок: 2.
И -> В -> Б -> Г -> М: 1 + 2 + 6 + 8 = 17. Длинный участок: 8.
И -> Г -> В -> М: 6 + 1 + 1 = 8. Длинный участок: 6.
И -> Г -> Б -> М: 6 + 6 + 3 = 15. Длинный участок: 6.
И -> Б -> М: (нет прямого пути И-Б, но есть И-А 1, А-Б 1, Б-М 3, итого 1+1+3=5)

Рассмотрим пути, где точка 'И' является начальной:

Кратчайший путь от И до М - это И -> В -> М, его длина равна 2.

Самый длинный участок на этом кратчайшем пути - это участки И-В (1) и В-М (1). Оба имеют длину 1.

Ответ: 1