Тема 1. Графы через матрицу смежности
1.03 Оптимизация маршрута
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы через матрицу смежности
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#6583

Путешественник пришел в 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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!