4. Между населёнными пунктами A, B, C, D, E, F построены дороги. Их длины: AB = 3, AC = 10, AD = 7, AE = 4, AF = 3, BC = 6, BF = 1, CD = 2, CE = 5, CF = 8, DE = 2, DF = 4. Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Каждый пункт можно посетить только один раз.

Проверим кратчайшие подходящие маршруты, не посещая пункты повторно. Например, маршрут A—B—C—D—F проходит через C и имеет длину 3 + 6 + 2 + 4 = 15.

Другие краткие варианты не дают меньшей длины: A—E—C—D—F имеет длину 4 + 5 + 2 + 4 = 15; A—E—D—C—B—F — 4 + 2 + 2 + 6 + 1 = 15. Если идти из C сразу в F, длина маршрута A—B—C—F уже равна 3 + 6 + 8 = 17. Следовательно, меньшего пути нет.

Ответ: 15