42. Тип 4 № 18243. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Строки и столбцы таблицы идут в порядке A, B, C, D, E, F; прочерк означает, что дороги нет: A —, 3, 4, —, —, 18; B 3, —, 3, —, —, —; C 4, 3, —, 4, —, —; D —, —, 4, —, 2, 6; E —, —, —, 2, —, 1; F 18, —, —, 6, 1, —. Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице.

Ищем путь от A до F, используя только дороги из таблицы.

1. По маршруту A—C—D—E—F длина равна 4 + 4? Проверяем таблицу: дорога C—D — 4, D—E — 2, E—F — 1. Итого 4 + 4 + 2 + 1 = 11 км.
2. По маршруту A—F длина равна 18 км; маршрут A—B—C—D—E—F равен 3 + 3 + 4 + 2 + 1 = 13 км.
3. Сравниваем допустимые маршруты: путь A—C—D—E—F длиной 11 км короче прямой дороги и пути через B. Более короткий обход через D—F даёт A—C—D—F: 4 + 4 + 6 = 14 км.

Ответ: 11 км.