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

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