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

Решение.

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

Выпишем связи между пунктами на основе таблицы:
$A$ связан с: $B (1)$, $C (5)$, $F (15)$
$B$ связан с: $A (1)$, $C (2)$
$C$ связан с: $A (5)$, $B (2)$, $D (3)$
$D$ связан с: $C (3)$, $E (2)$, $F (3)$
$E$ связан с: $D (2)$, $F (2)$
$F$ связан с: $A (15)$, $D (3)$, $E (2)$

Этап 1: Ищем кратчайший путь из $A$ в $D$.
Рассмотрим возможные варианты:
1) $A \rightarrow C \rightarrow D$. Длина: $5 + 3 = 8$ км.
2) $A \rightarrow B \rightarrow C \rightarrow D$. Длина: $1 + 2 + 3 = 6$ км.
Других более коротких путей нет (прямой дороги $A-D$ не существует). Кратчайший путь $A \rightarrow D$ равен $6$ км.

Этап 2: Ищем кратчайший путь из $D$ в $F$.
Рассмотрим возможные варианты:
1) $D \rightarrow F$. Длина: $3$ км.
2) $D \rightarrow E \rightarrow F$. Длина: $2 + 2 = 4$ км.
Кратчайший путь $D \rightarrow F$ равен $3$ км.

Этап 3: Вычисляем итоговую длину пути.
Сложим результаты двух этапов: $6$ км (путь $A \rightarrow B \rightarrow C \rightarrow D$) + $3$ км (путь $D \rightarrow F$) = $9$ км.
Проверим условие: каждый пункт посещён не более одного раза. Путь $A \rightarrow B \rightarrow C \rightarrow D \rightarrow F$ проходит через пункты $A, B, C, D, F$. Условие соблюдено.

Ответ: 9 км.

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