Задание 2. Вы стоите на автовокзале в деревне Ахово. Вам надо как можно скорее попасть в Ухово. Сейчас восемь утра, перед вами расписание автобусов. Прямой автобус в Ухово ушёл из Ахова полчаса назад. Надо искать варианты с пересадками. Вариантов много, постараемся не запутаться. Нарисуем дерево. Корнем его будет Ахово (А). Вершинами первого уровня будут те населённые пункты, куда можно попасть из А после 8:00. Обязательно укажем около каждой вершины время, в которое мы можем в неё попасть. Нам не придётся перебирать все варианты: ветку можно «обрезать», если у нас есть более быстрый путь в конечный пункт. Начало дерева будет выглядеть так: A Б 9:20 y 14:30 O 11:20 B 13:10 Задача уже решена? Нет: вдруг есть другой, более быстрый путь? Пока мы знаем только то, что вершины, достижимые после 14:30, нам неинтересны. Достройте дерево самостоятельно. Каким может быть самое раннее время прибытия в Ухово?

Решение:

Нам нужно найти самый быстрый путь из Ахово (А) в Ухово. Мы можем использовать информацию из расписания и построенное дерево, чтобы найти оптимальный маршрут. Вершины, достижимые после 14:30, нас не интересуют.

Проанализируем возможные маршруты:

1. Прямой путь из Ахово (А) в Ухово: такого варианта нет в расписании после 8:00.
2. Путь через населённые пункты первого уровня (доступные из А после 8:00):
• А → Б: Из Ахово (А) в Бухово (Б) есть автобус в 6:20 (прибытие 7:00) и в 11:15 (прибытие 14:30). Нас интересует только время после 8:00. Отправление из А в 11:15, прибытие в Бухово в 14:30. Из Бухово в Ухово нет прямых рейсов.
• А → О: Из Ахово (А) в Охово (О) нет прямых рейсов после 8:00.
• А → В: Из Ахово (А) в Вахово (В) есть рейс в 8:10 (прибытие 9:20). Из Вахово (В) в Ухово есть рейс в 14:40 (прибытие 14:40). Этот маршрут занимает много времени.
• А → У: Из Ахово (А) в Ухово (У) есть рейсы: 7:30 (прибытие 11:10) и 10:10 (прибытие 11:20). Мы можем отправиться в 10:10 и прибыть в Ухово в 11:20.

Пересмотрим дерево с учетом того, что мы ищем самый быстрый путь из Ахово (А) в Ухово. Нас интересуют только пункты, куда можно попасть после 8:00.

Варианты из Ахово (А) после 8:00:

• A → У: Отправление в 10:10, прибытие в Ухово в 11:20.

Рассмотрим возможные пересадки:

• Из Ахово (А) в Бухово (Б): Автобус из Ахово в Бухово отправляется в 11:15 и прибывает в 14:30. Из Бухово в Ухово нет рейсов.
• Из Ахово (А) в Охово (О): Нет рейсов из Ахово в Охово после 8:00.
• Из Ахово (А) в Вахово (В): Отправление в 8:10, прибытие в Вахово в 9:20. Из Вахово в Ухово есть рейс в 14:40 (прибытие 14:40). Этот путь позже, чем прямой.

Дерево с указанием времени прибытия в промежуточные пункты:

A (8:00)

• → У (11:20)
• → Б (14:30) (но из Б нет прямого пути в Ухово, и время уже поздно)
• → В (9:20) (дальше из В в Ухово только в 14:40, что позже 11:20)

Наиболее быстрый путь из Ахово в Ухово - это прямой рейс отправлением в 10:10, прибывающий в 11:20.

Ответ: 11:20.