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

Рассмотрим пути из И в М. Прямой путь И—М имеет длину 8.

Путь И—Г—М имеет длину 6 + 1 = 7. Через Б получаем И—Б—М: 1 + 3 = 4.

Путь И—А—В—Б—М имеет длину 1 + 1 + 2 + 3 = 7, а путь И—Б—В—А—И не ведёт к М короче, чем маршрут через Б. Следовательно, кратчайшая длина равна 4; кратчайший маршрут — И—Б—М. Его участки имеют длины 1 и 3, поэтому самый длинный из них равен 3.

Ответ: 3.