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

Найдём кратчайшие пути от И до М и сравним их самые длинные участки.

1. Через Б: И–Б–М имеет длину 1 + 3 = 4; самый длинный участок равен 3.
2. Через Г: И–Г–М имеет длину 6 + 1 = 7.
3. Через Б и В: И–Б–В–А–И не ведёт к М короче, чем путь через Б; путь И–Б–М уже имеет длину 4.
4. Другие доступные пути, например И–Б–В–А–И–Б–М или И–Г–М с обходом, не короче 4.

Кратчайший путь — И–Б–М, его общая длина равна 4. Длины участков на нём: 1 и 3.

Ответ: 3