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

Рассмотрим все возможные пути между пунктами А и С и выберем кратчайший из них.

1. Путь A-D-B-C. Длина пути: 3 + 0 + 1 = 4.
2. Путь A-D-E-B-C. Длина пути: 3 + 0 + 4 + 1 = 8.
3. Путь A-E-B-C. Длина пути: 5 + 4 + 1 = 10.
4. Путь A-E-F-C. Длина пути: 5 + 0 + 3 = 8.
5. Путь A-E-F-B-C. Длина пути: 5 + 0 + 1 + 1 = 7.

Кратчайший путь между пунктами A и C равен 4.

Ответ: 4