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

Решение.

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

Шаг 1. Поиск кратчайшего пути из $A$ в $C$.
Выпишем все возможные варианты дорог из таблицы:
1) Прямой путь: $A \to C$ длиной $6$.
2) Через пункт $B$: $A \to B \to C$. Длина: $5 + 5 = 10$.
3) Через пункт $E$: $A \to E \to C$. Длина: $3 + 2 = 5$.
4) Через пункты $E$ и $B$: $A \to E \to B \to C$. Длина: $3 + 4 + 5 = 12$.
Самый короткий путь из $A$ в $C$ — это маршрут $A \to E \to C$ длиной $5$.

Шаг 2. Поиск кратчайшего пути из $C$ в $D$.
Важно помнить, что мы уже посетили пункты $A$ и $E$, поэтому возвращаться в них нельзя.
1) Прямой путь: $C \to D$ длиной $2$.
2) Через пункт $B$: $C \to B \to D$. Но дороги $B \to D$ в таблице нет.
Самый короткий (и единственный подходящий) путь из $C$ в $D$ — это прямой путь длиной $2$.

Шаг 3. Вычисление итоговой длины.
Сложим длины двух участков пути:
$L = (A \to E \to C) + (C \to D)$
$L = 5 + 2 = 7$.

Проверим, нет ли других вариантов. Если мы пойдём $A \to C$ напрямую (длина $6$), то путь до $D$ составит $6 + 2 = 8$, что длиннее. Если пойдём $A \to D$ напрямую, мы не посетим обязательный пункт $C$.

Таким образом, кратчайший путь: $A \to E \to C \to D$.

Ответ: 7

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