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

Чтобы найти кратчайший путь из A в F через C, нужно рассмотреть все возможные пути из A в F через C и выбрать кратчайший из них.

Возможные пути:

1. A -> C -> F: 2 + 5 = 7
2. A -> B -> C -> F: 3 + 3 + 5 = 11
3. A -> C -> B -> F: 2 + 3 + 5 = 10
4. A -> B -> C -> D -> F : 3 + 3 + 1 + 6 = 13
5. A -> B -> C -> E -> F : 3 + 3 + 5 + 1 = 12
6. A -> C -> B -> D -> F: 2 + 3 + 1 + 6 = 12
7. A -> C -> B -> E -> F: 2 + 3 + 0 + 1 = 6 (пути B -> E нет)
8. A -> D -> C -> F: Нет пути между A и D
9. A -> D -> C -> B -> F: Нет пути между A и D

Другие комбинации будут длиннее, так как включают больше промежуточных пунктов или невозможны, т.к. между некоторыми пунктами нет дорог.

Сравнив длины всех возможных путей, видим, что кратчайший путь равен 7.