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

Рассмотрим пути из A в F, проходящие через C. Из C до F можно ехать напрямую за 9 км или через D и E: C–D–E–F, длина которого 2 + 3 + 4 = 9 км. Кратчайший путь из A в C — A–B–C: 3 + 1 = 4 км.

Тогда путь A–B–C–D–F имеет длину 3 + 1 + 2 + 6 = 12 км. Другой кратчайший вариант — A–B–C–D–E–F: 3 + 1 + 2 + 3 + 4 = 13 км. Путь A–C–F также длиннее: 5 + 9 = 14 км.

Ответ: 12 км.