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

Решение.

Для решения задачи нам необходимо найти кратчайший путь из пункта $A$ в пункт $F$, который обязательно проходит через пункт $C$. Это означает, что задачу можно разделить на два этапа:
1) Найти кратчайший путь от $A$ до $C$.
2) Найти кратчайший путь от $C$ до $F$.
Затем мы сложим длины этих путей.

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

Этап 2: Путь из C в F.
Теперь ищем кратчайший путь из $C$ в $F$. Важно помнить, что мы не можем возвращаться в пункты $A$ и $B$, так как по условию каждый пункт можно посетить только один раз.
Из $C$ есть дороги:
— $C \to D$ длиной $1$.
— $C \to E$ длиной $3$.
Рассмотрим продолжение пути из $D$:
— Из $D$ можно поехать в $E$: $D \to E$ длиной $1$.
— Из $E$ можно поехать в $F$: $E \to F$ длиной $2$.
Получаем маршрут: $C \to D \to E \to F$. Его длина: $1 + 1 + 2 = 4$ км.
Проверим другие варианты:
— Путь $C \to E \to F$ имеет длину $3 + 2 = 5$ км (это длиннее).
— Прямой дороги из $C$ в $F$ нет.
Таким образом, кратчайшее расстояние $C \to F = 4$ км.

Итоговый расчет:
Сложим длины двух участков пути:
$L = (A \to B \to C) + (C \to D \to E \to F)$
$L = 5 \text{ км} + 4 \text{ км} = 9 \text{ км}$.

Ответ: 9 км

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