53.КРВ2. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз. Таблица: AB = 4, AC = 7, AD = 2, AE = 11, BC = 4, CD = 4, CE = 3, DE = 2.

Требуется пройти из A в E через C, не посещая ни один пункт дважды. Перечислим допустимые маршруты с посещением C.

Через B: A–B–C–E = 4 + 4 + 3 = 11 км; A–B–C–D–E = 4 + 4 + 4 + 2 = 14 км.

Начав с A–C: A–C–E = 7 + 3 = 10 км; A–C–B–…–E невозможно, поскольку из B, кроме уже посещённого C, нет дороги к D или E. Маршрут A–C–D–E = 7 + 4 + 2 = 13 км; вариант A–C–D–B–…–E невозможен, так как дороги B–E нет.

Начав с A–D, можно продолжить через C: A–D–C–E = 2 + 4 + 3 = 9 км; A–D–C–B–…–E невозможно, поскольку B соединён только с уже посещёнными A и C. Маршрут A–D–E не проходит через C.

Минимальная длина подходящего пути — 9 км, по маршруту A–D–C–E.

Ответ: 9 км.