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

Нам нужно найти кратчайший путь из A в E через C. Возможные пути: 1. A → C → E: Длина пути = 20 + 0 = 20 + 0 = 28 = 48 2. A → B → C → E : Длина пути = 12 + 18 + 0 = 12 + 18 + 0 = 28 = 58 3. A → C → D → E: Длина пути = 20 + 0 = 10 + 14 = 44 4. A → D → C → E: Длина пути = 15 + 10 + 0 = 15 + 10 + 0 = 28 = 53 5. A -> B -> C : 12 + 18 = 30, далее C -> E : 0 = 28, итого 30 + 28 = 58 6. A -> C -> B : 20 + 18 = 38, далее B -> E : 0 = 15, итого 38 + 15 = 53 7. A -> D -> C : 15 + 10 = 25, далее C -> E : 0 = 28, итого 25 + 28 = 53 Так как нужно обязательно пройти через C, рассмотрим варианты пути из A в E через C: * A -> C -> E: 20 + 28 = 48 * A -> B -> C -> E: 12 + 18 + 0 = 12 + 18 + 0 = 28 = 58 * A -> D -> C -> E: 15 + 10 + 0 = 15 + 10 + 0 = 28 = 53 Теперь рассмотрим варианты путей из A в C, а затем из C в E: * A -> C = 20 * C -> E = 28 Итого: 20 + 28 = 48. Рассмотрим другие пути: * A -> B -> C = 12 + 18 = 30 * A -> D -> C = 15 + 10 = 25 Теперь, чтобы добраться до E: * B -> E = 15, итого 30 + 15 = 45 * D -> E = 14, итого 25 + 14 = 39 Получается, что маршруты A -> B -> C -> E и A -> D -> C -> E не подходят, так как не проходят через C. Сравним пути, проходящие через C: * A -> C -> E = 48 Теперь ищем другие варианты: Путь A -> D -> E = 15 + 14 = 29 - не проходит через C. Путь A -> B -> E = 12 + 15 = 27 - не проходит через C. Однако нам нужно обязательно пройти через C. Поэтому рассмотрим все возможные комбинации с C: 1. A -> C -> E = 20 + 28 = 48 2. A -> B -> C, затем C -> E: 12 + 18 + 28 = 58. Длиннее. 3. A -> D -> C, затем C -> E: 15 + 10 + 28 = 53. Длиннее. Следовательно, кратчайший путь A -> C -> E = 48. Ответ: 48