Тип 4 № 37257. Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.

Нужно пройти из A в E, посетив каждый пункт не более одного раза. Подходящий маршрут A–D–B–C–E имеет длину 4 + 5 + 1 + 5 = 15 км. Другой возможный порядок, A–C–B–D–E, даёт 3 + 1 + 5 + 7 = 16 км; маршруты с отсутствующими дорогами невозможны.

Ответ: 15 км.