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

Рассмотрим основные пути из пункта И в пункт М:

• И → Б → М: 1 + 3 = 4;
• И → В → Б → М: 1 + 2 + 3 = 6;
• И → Г → М: 6 + 1 = 7;
• И → М: 8.

Кратчайший путь имеет длину 4: И → Б → М. Его участки имеют длины 1 и 3, поэтому самый длинный участок этого пути равен 3.

Ответ: 3