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

Решение.

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

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

Шаг 2: Поиск кратчайшего пути из $C$ в $E$.
Теперь найдем кратчайший путь из точки $C$ в точку $E$, учитывая, что мы не можем возвращаться в пункты, которые уже посетили (если мы шли через $B$, то $B$ использовать нельзя).
1) Прямой путь: $C \to E$. Его длина равна $3$ км.
2) Путь через $D$: $C \to D \to E$. Длина: $4 + 1 = 5$ км.
3) Путь через $B$: $C \to B \to E$. Длина: $1 + 5 = 6$ км.
Самый короткий вариант из $C$ в $E$ — это прямой путь длиной $3$ км.

Шаг 3: Расчет общей длины пути.
Сложим длины двух участков:
Длина пути = (расстояние $A \to C$) + (расстояние $C \to E$)
Длина пути = $3 \text{ км} + 3 \text{ км} = 6 \text{ км}$.

Проверим, нет ли других комбинаций. Если мы идем $A \to B \to C \to E$, длина также составит $2 + 1 + 3 = 6$ км. Если мы идем $A \to C \to E$, длина составит $3 + 3 = 6$ км. Оба варианта удовлетворяют условию прохода через $C$ и посещения каждого пункта один раз.

Ответ: 6

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