Между населёнными пунктами построены дороги,
протяжённость которых приведена в таблице. (Отсутствие числа в таблице
означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами и (при условии, что
передвигаться можно только по построенным дорогам).
В ответе укажите номер, соответствующий полученному значению.
Показать разбор и ответ
Большинство путей из в ведут через Найдем кратчайший из этих путей, а потом рассмотрим остальные пути. Сначала найдем кратчайший путь из в потом – кратчайший путь из в
Из в ведут пути (не стоит рассматривать пути, которые больше одного раза проходят через один и тот же пункт). Вот эти пути в алфавитном порядке:
длина пути
длина пути
длина пути
длина пути
Кратчайший из этих путей – путь длиной
Из в ведет единственный маршрут длиной
Таким образом, кратчайший маршрут из в через – это маршрут
длиной
Маршруты из в не проходящие через должны использовать дороги и Длина дороги равна Маршрут через должен проходить через Кратчайший путь в – это маршрут длиной Значит, кратчайший маршрут в через – это маршрут который имеет длину
Таким образом, длина кратчайшего маршрута из в равна Есть два таких маршрута: и
Ответ: 3
Это задание решали 51 раз. С ним справились 20% пользователей.