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

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

Шаг 1: Анализ таблицы.
Выпишем доступные дороги и их длины:
$A-B = 1$
$A-C = 4$
$A-D = 3$
$A-E = 7$
$B-C = 2$
$B-D = 5$
$C-D = 3$
$D-E = 2$

Шаг 2: Поиск кратчайшего пути из A в C.
Рассмотрим возможные варианты пути из $A$ в $C$, не заходя в $E$ (так как $E$ — конечная точка):
1) Прямой путь: $A \to C$. Длина = $4$ км.
2) Путь через $B$: $A \to B \to C$. Длина = $1 + 2 = 3$ км.
3) Путь через $D$: $A \to D \to C$. Длина = $3 + 3 = 6$ км.
Кратчайший путь из $A$ в $C$ равен $3$ км (маршрут $A \to B \to C$).

Шаг 3: Поиск кратчайшего пути из C в E.
Теперь найдем кратчайший путь из $C$ в $E$, не возвращаясь в уже посещенные пункты ($A$ и $B$):
1) Путь через $D$: $C \to D \to E$. Длина = $3 + 2 = 5$ км.
2) Прямого пути $C \to E$ в таблице нет.
Других вариантов, не посещая пункты повторно, нет. Кратчайший путь из $C$ в $E$ равен $5$ км.

Шаг 4: Расчет общей длины пути.
Сложим длины двух участков: $(A \to B \to C) + (C \to D \to E)$.
Общая длина = $3 \text{ км} + 5 \text{ км} = 8 \text{ км}$.

Проверим, нет ли других вариантов. Если мы пойдем $A \to C$ напрямую ($4$ км), то путь $A \to C \to D \to E$ составит $4 + 3 + 2 = 9$ км, что длиннее. Если пойдем через $D$ в начале ($A \to D \to C$), то мы не сможем попасть в $E$, не посетив $D$ второй раз, что запрещено условием.

Ответ: 8 км.

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