Задание №4 — Теоретические основы информатики

Решение.

Для решения этой задачи мы построим дерево всех возможных путей из пункта $A$ в пункт $D$, учитывая условие, что в каждый пункт можно заходить не более одного раза. Выпишем все доступные дороги и их длины из таблицы:

$A-B: 6$
$A-E: 3$
$B-C: 2$
$B-D: 5$
$B-E: 1$
$C-D: 2$
$D-E: 6$

Теперь проследим все возможные маршруты из точки $A$ в точку $D$:

1) Прямого пути $A-D$ нет. Рассмотрим пути через ближайшие к $A$ пункты ($B$ и $E$).

2) Пути через пункт $B$:
— $A \to B \to D$. Длина: $6 + 5 = 11$ км.
— $A \to B \to C \to D$. Длина: $6 + 2 + 2 = 10$ км.
— $A \to B \to E \to D$. Длина: $6 + 1 + 6 = 13$ км.

3) Пути через пункт $E$:
— $A \to E \to D$. Длина: $3 + 6 = 9$ км.
— $A \to E \to B \to D$. Длина: $3 + 1 + 5 = 9$ км.
— $A \to E \to B \to C \to D$. Длина: $3 + 1 + 2 + 2 = 8$ км.

Сравним полученные результаты: $11$, $10$, $13$, $9$, $9$ и $8$. Самым коротким оказался путь $A \to E \to B \to C \to D$, его длина составляет $8$ км.

Ответ: 8 км

Источник: ФИПИ