Задание EGEINF59FF2B: Графы, таблицы и маршруты

Решение.
Длина маршрута равна сумме длин его дорог. Отсутствие числа означает отсутствие прямого соединения, а не дорогу нулевой длины. Все длины положительны, поэтому обход с возвращением в уже посещённый пункт только увеличивает путь.
Найдём кратчайшие расстояния от A до всех пунктов. Обозначим их текущие оценки через d. В начале d(A) = 0, а остальные оценки равны ∞: маршрут пока не найден.
Каждый раз выбираем ещё не обработанный пункт с наименьшей оценкой. Его расстояние уже окончательно: любая дорога через более далёкий пункт не даст меньшую длину. Для соседа Y пункта X сравниваем прежнее d(Y) с d(X) + длина дороги XY и оставляем меньшее.
Обрабатываем A: d(A)=0, d(B)=3, d(C)=2, d(D)=1, d(E)=∞, d(F)=7.
Обрабатываем D: d(A)=0, d(B)=3, d(C)=2, d(D)=1, d(E)=6, d(F)=6.
Обрабатываем C: d(A)=0, d(B)=3, d(C)=2, d(D)=1, d(E)=6, d(F)=5.
Обрабатываем B: d(A)=0, d(B)=3, d(C)=2, d(D)=1, d(E)=6, d(F)=5.
Обрабатываем F: d(A)=0, d(B)=3, d(C)=2, d(D)=1, d(E)=6, d(F)=5.
Обрабатываем E: d(A)=0, d(B)=3, d(C)=2, d(D)=1, d(E)=6, d(F)=5.
Минимальная длина от A до F равна 5. Она достигается маршрутом A → C → F: 2 + 3 = 5.
Проверка нижней оценки: для каждой разрешённой дороги X–Y итоговые значения удовлетворяют d(Y) ≤ d(X) + длина XY в обоих направлениях. Складывая эти неравенства вдоль любого пути от начала, получаем, что его длина не меньше d(F). Показанный маршрут достигает этой оценки, значит, он действительно кратчайший.
Варианты ответа: 1) 5, 2) 7, 3) 3, 4) 9. Число 5 стоит под номером 1. В ответ записываем номер варианта.
Ответ: 1.