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

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