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

Решение.

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

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

Этап 2: Путь из $C$ в $F$.
Теперь найдём кратчайший путь из точки $C$ в точку $F$, не используя пункты $A$ и $B$, так как мы их уже посетили (по условию пункт можно посетить только один раз).
Рассмотрим доступные варианты из $C$:
1) Напрямую: $C \to F$ длиной $9$ км.
2) Через пункт $D$: $C \to D \to F$. Длина: $2 + 6 = 8$ км.
3) Через пункты $D$ и $E$: $C \to D \to E \to F$. Длина: $2 + 3 + 2 = 7$ км.
4) Через пункт $E$: Дороги из $C$ в $E$ напрямую нет.
Самый короткий путь из $C$ в $F$ — это маршрут $C \to D \to E \to F$ длиной $7$ км.

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

Проверим, нет ли других маршрутов. Любой другой путь либо не будет содержать точку $C$, либо будет длиннее из-за использования более протяжённых дорог (например, прямой дороги $A \to D$).

Ответ: 11 км.

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