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

Решение.

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

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

Этап 2: Ищем кратчайший путь из $C$ в $F$.
Из пункта $C$ можно попасть в следующие пункты:
— Напрямую в $F$: дорога отсутствует (в таблице нет пересечения $C$ и $F$).
— Через пункт $D$: $C \rightarrow D \rightarrow F$. Длина: $1 + 6 = 7$ км.
— Через пункт $E$: $C \rightarrow E \rightarrow F$. Длина: $3 + 4 = 7$ км.
— Через пункт $B$: $C \rightarrow B \rightarrow \dots$ (но из $B$ ведут дороги только в $A$ и $C$, которые мы уже учитывали или посетили).
Минимальное расстояние от $C$ до $F$ составляет $7$ км.

Этап 3: Вычисление общей длины пути.
Сложим результаты двух этапов:
$L = L(A \rightarrow C) + L(C \rightarrow F)$
$L = 4 \text{ км} + 7 \text{ км} = 11 \text{ км}$.

Проверим условие: каждый пункт посещён не более одного раза.
Вариант 1: $A \rightarrow B \rightarrow C \rightarrow D \rightarrow F$ (длина $2+2+1+6 = 11$).
Вариант 2: $A \rightarrow B \rightarrow C \rightarrow E \rightarrow F$ (длина $2+2+3+4 = 11$).
Оба маршрута соответствуют условиям задачи и имеют длину $11$ км.

Ответ: 11 км.

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