Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Нужно найти кратчайший путь из A в E через C. Возможные пути: 1. A -> C -> E: Длина пути = 9 + 0 = 9 (Так как нет дороги напрямую из C в E в таблице) 2. A -> B -> C -> E: Длина пути = 3 + 8 + 0 = 11 (Так как нет дороги напрямую из C в E в таблице) 3. A -> D -> C -> E: Длина пути = 19 + 10 + 0 = 29 (Так как нет дороги напрямую из C в E в таблице) 4. A -> C -> B -> E: Длина пути = 9 + 8 + 25 = 42 5. A -> C -> D -> E: Длина пути = 9 + 10 + 8 = 27 Теперь рассмотрим другие пути проходящие через C: 1. A -> C -> E: Прямого пути из C в E нет, но есть путь E -> C = нет данных. Мы ищем кратчайший путь, и можем двигаться только по дорогам, указанным в таблице. Имеем следующие пути через С: 1. A -> C -> D -> E = 9 + 10 + 8 = 27 2. A -> C -> B -> E = 9 + 8 + 25 = 42 Кратчайший путь A -> C -> D -> E, его длина 27. Ответ: 27