Задача к ЕГЭ по информатике на тему «графы через матрицу смежности» №1

Путешественник пришел в 09:00 на автостанцию поселка Яблоново и увидел следующее расписание автобусов:

PIC

По таблице определите самое позднее время, в которое путешественник может оказаться в поселке Березовое:

1) 12:20

2) 12:00

3) 12:10

4) 12:40

Первый вариант решения

Рассмотрим каждый маршрут, по которому может поехать путешественник, отдельно:

Первый маршрут: Яблоново-Осиново (9:20-10:00) → Осиново-Кленово (10:00-11:00) → Кленово-Березовое (11:45-12:10);

Второй маршрут: Яблоново-Осиново (9:20-10:00) → Осиново-Березовое (11:20-12:20);

Третий маршрут: Яблоново-Кленово (10:50-11:40) → Кленово-Березовое (11:45-12:10).

Заметим, что четвертый маршрут (Яблоново-Елкино (отправление в 8:10) → Елкино-Дубовое      → Дубовое-Кленово → Кленово-Березовое) нам не подходит, так как отправление происходит раньше, чем путешественник пришел на станцию. Из первых трех подходящих маршрутов выберем самое позднее время прибытия – 12:20. Значит, наш ответ под цифрой 1.

Второй вариант решения

Для удобства представим все маршруты из Яблоново в виде графа:

PIC

Верхняя ветка не подходит, т.к. отправление из Яблонево происходит раньше 9:00. Из двух оставшихся выбираем самое позднее время прибытия в Березовое – 12:20. Значит, наш ответ под цифрой 1.

Ответ: 1
Оцените статью
Я решу все!