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

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

Посмотрим на таблицу и выпишем все возможные дороги из начального пункта $A$:
Из $A$ можно попасть только в пункт $B$ (длина дороги — $4$ км).

Теперь продолжим маршруты из пункта $B$:
1. $A \to B \to C$ (длина $4 + 4 = 8$ км)
2. $A \to B \to E$ (длина $4 + 1 = 5$ км)

Рассмотрим продолжение первого маршрута ($A \to B \to C$):
Из $C$ можно поехать в $D$ или $E$.
— $A \to B \to C \to D$: длина $4 + 4 + 1 = 9$ км.
— $A \to B \to C \to E$: длина $4 + 4 + 2 = 10$ км. Из $E$ можно попасть в $D$, тогда путь $A \to B \to C \to E \to D$ составит $10 + 3 = 13$ км.

Рассмотрим продолжение второго маршрута ($A \to B \to E$):
Из $E$ можно поехать в $C$ или $D$.
— $A \to B \to E \to D$: длина $4 + 1 + 3 = 8$ км.
— $A \to B \to E \to C$: длина $4 + 1 + 2 = 7$ км. Из $C$ можно попасть в $D$, тогда путь $A \to B \to E \to C \to D$ составит $7 + 1 = 8$ км.

Выпишем все найденные пути до пункта $D$ и их итоговую длину:
1. $A \to B \to C \to D$: $9$ км.
2. $A \to B \to C \to E \to D$: $13$ км.
3. $A \to B \to E \to D$: $8$ км.
4. $A \to B \to E \to C \to D$: $8$ км.

Сравнивая результаты, видим, что минимальное значение длины пути равно $8$ км.

Ответ: 8

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