Задание OGEINFE6DE46: Кратчайший путь по таблице дорог

1. Прочитаем таблицу дорог.
Нужно пройти из A в F. Число на пересечении строки и столбца — длина прямой дороги между соответствующими пунктами. Пустая клетка означает, что такой дороги нет; считать её дорогой нулевой длины нельзя. Таблица симметрична, поэтому каждую дорогу записываем один раз:
A—B: 3; A—C: 5; A—F: 15; B—C: 1; B—D: 4; C—D: 2; C—F: 9; D—E: 3; D—F: 6; E—F: 4.
Все длины измеряются в километрах. Каждый пункт разрешено посетить только один раз. Кроме того, маршрут обязан содержать пункт C.

2. Переберём допустимые маршруты.
Начинаем в исходном пункте и по очереди выбираем каждую существующую дорогу в ещё не посещённый пункт. Продолжаем до конечного пункта; если дальше двигаться нельзя, возвращаемся к последнему выбору. Так рассматриваем все простые пути, а не только маршруты с наименьшим числом дорог. Из полученных путей оставляем только проходящие через C. Для каждого оставшегося пути складываем длины его дорог:
A—B—C—D—E—F: 3 + 1 + 2 + 3 + 4 = 13 км.
A—B—C—D—F: 3 + 1 + 2 + 6 = 12 км.
A—B—C—F: 3 + 1 + 9 = 13 км.
A—B—D—C—F: 3 + 4 + 2 + 9 = 18 км.
A—C—B—D—E—F: 5 + 1 + 4 + 3 + 4 = 17 км.
A—C—B—D—F: 5 + 1 + 4 + 6 = 16 км.
A—C—D—E—F: 5 + 2 + 3 + 4 = 14 км.
A—C—D—F: 5 + 2 + 6 = 13 км.
A—C—F: 5 + 9 = 14 км.

3. Сравним длины.
Проверены все допустимые пути из A в F; их количество — 9. Полученные длины: 13, 12, 13, 18, 17, 16, 14, 13, 14. Наименьшая из них равна 12 км. Она достигается на маршруте A—B—C—D—F. Ни один путь не пропущен: на каждом шаге рассмотрены все соседние ещё не посещённые пункты, а ограничения условия проверены до сравнения длин.

4. Проверка.
Проверим один кратчайший маршрут по исходной таблице: A—B = 3, B—C = 1, C—D = 2, D—F = 6.
Сумма длин: 3 + 1 + 2 + 6 = 12 км. Начало маршрута — A, конец — F; все дороги существуют, все пункты в маршруте различны. Обязательный пункт C присутствует. В ответ требуется длина пути, поэтому записываем только число.

Ответ: 12.