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

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