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

Решение.

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

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

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

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

Проверим, нет ли других комбинаций. Любой другой путь будет длиннее (например, если идти $A \rightarrow C$ напрямую за $5$ км, то общий путь составит $5 + 8 = 13$ км).

Ответ: 12 км

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