Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

3. Графы через матрицу смежности

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Нахождение маршрута с помощью расписания

Задание 1 #10845

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

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

1) 12:20

2) 12:00

3) 12:10

4) 12:40

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

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

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

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

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

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

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

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

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

Ответ: 1

Задание 2 #10846

Курьеру необходимо доставить посылку из поселка Приволжское в поселок Кольцово. У него есть несколько вариантов маршрута:

Определите стоимость самого быстрого маршрута в у.е.

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

Определим самый быстрый маршрут:

Первый маршрут: Приволжское-Ванино-Яшкино-Кольцово: 60+30+40 = 130 минут;

Второй маршрут: Приволжское-Ванино-Софрино-Кольцово: 60+45+50 = 155 минут;

Третий маршрут: Приволжское-Яшкино-Кольцово: 70+40 = 110 минут;

Четвертый маршрут: Приволжское-Яшкино-Ванино-Софрино-Кольцово: 70+30+45+50 = 195 минут.

Поскольку самым быстрым является третий маршрут, считаем его стоимость: 46+35 = 81 у.е.

Ответ: 81

Задание 3 #10847

Путешественник оказался в аэропорту Озерово в 5:00. Ему необходимо попасть в аэропорт Синицыно как можно скорее. Считается, что путешественник успевает совершить пересадку, если между рейсами проходит не менее 2-ух часов.

Определите, через какое наименьшее количество часов путешественник может попасть в аэропорт Синицыно.

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

Т.к. путешественник окаазался в Озерово в 5:00, на прямой рейс он не успевает. Рассмотрим два оставшихся маршрута:

Первый маршрут: Озерово-Грирьево (6:00-9:00) \(\rightarrow\) Григорьево-Синицыно (11:00-14:00). Между рейсами ровно 2 часа, значит, путешественник успевает совершить пересадку. Считаем затраченное время на данный маршрут: 3 часа (Озерово-Григорьево) + 3 часа (Григорьево-Синицыно) + 2 часа (пересадка) = 8 часов;

Второй маршрут: Озерово-Соколиное (5:20-7:20) \(\rightarrow\) Соколиное-Синицыно (9:00-13:00). Временной промежуток между рейсами менее 2-ух часов, значит, путешественник не успеет совершить пересадку, следовательно, данный маршрут нам не подходит.

Значит, наш ответ – 8.

Ответ: 8

Задание 4 #10848

Путешественник пришел на автостанцию поселка Алексеево в 7:00 и увидел следующее расписание автобусов с прейскурантом:

Определите стоимость самого быстрого маршрута до поселка Горное в у.е.

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

Определим самый быстрый маршрут:

Первый маршрут: Алекссево-Горное (7:00-12:00) = 5 часов;

Второй маршрут: Алексеево-Солнечный (6:50-8:50) \(\rightarrow\) Солнечный-Горное (9:00-12:00). Маршрут не подходит, т.к. на автостанцию путешественник пришел только в 7:00;

Третий маршрут: Алексеево-Редкино (7:00-8:00) \(\rightarrow\) Редкино-Быково (8:15-9:30) \(\rightarrow\) Быково-Горное (9:40-10:30) = 1 час + 1 час 15 минут + 50 минут = 3 часа 05 минут.

Самый быстрый маршрут – третий. Считаем его стоимость: 15 + 20 + 15 = 50 у.е.

Ответ: 50

Задание 5 #10849

Компания друзей из поселка Приволжский решила отправиться в поселок Речное. На вокзале им предложили следующие маршруты:

Определите, сколько часов компания будет находится в пути, если выберет самый дешевый маршрут.

 

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

Определим самый дешевый маршрут:

Первый маршрут: 250 (Приволжский-Озерово) + 300 (Озерово-Речное) = 550 у.е.;

Второй маршрут: 750 у.е. (Приволжский-Речное);

Третий маршрут: 380 (Приволжский-Подберезное) + 100 (Подберезное-Лисино) + 500 (Лисино-Речное) = 980 у.е.

Самый дешевый маршрут – первый. Считаем время, затраченное на дорогу: 3 часа + 2 часа = 5 часов.

Ответ: 5

Задание 6 #10850

Курьеру необходимо доставить посылку из поселка Озерный в поселок Соколиное. У него есть несколько вариантов маршрута:

Определите, сколько времени (в минутах) курьер проведет в дороге, если выберет самый дорогой маршрут.

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

Определим самый дорогой маршрут:

Первый маршрут: 50 (Озерный-Луговое) + 30 (Луговое-Сергеево) + 40 (Сергеево-Соколиное) = 120 у.е.;

Второй маршрут: 50 (Озерный-Луговое) + 15 (Луговое-Орехово) + 30 (Орехово-Соколиное) = 95 у.е.

Самый дорогой маршрут – первый. Считаем время, затраченное на дорогу: 30 + 20 + 70 = 120 минут.

Ответ: 120

Задание 7 #10851

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

По таблице определите стоимость маршрута, выбрав который, путешественник раньше всего окажется в поселке Рощино.

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

Определим маршрут, по котрому путешественник раньше всего попадет в поселок Рощино:

Первый маршрут: Иваново-Петрово (6:00-7:00) \(\rightarrow\) Петрово-Ракитино (6:45-8:30) \(\rightarrow\) Ракитино-Рощино (9:00-10:00). Данный маршрут не подходит, т.к. в поселке Петрово путешественник окажется только в 7:00, а отправление оттуда в 6:45;

Второй маршрут: Иваново-Петрово (6:00-7:00) \(\rightarrow\) Петрово-Советово (7:20-8:00) \(\rightarrow\) Советово-Рощино (7:30-9:00). Маршрут не подходит, т.к. в поселке Советово путешественник окажется только в 8:00, а отправление оттуда в 7:30;

Третий маршрут: Иваново-Петрово (6:00-7:00) \(\rightarrow\) Петрово-Рамово (8:00-9:30) \(\rightarrow\) Рамово-Рощино (10:00-11:00).

Самый быстрый и единственный возможный маршрут – третий. Количество у.е., затраченных на поездку по данному маршруту: 15 + 20 + 30 = 65 у.е.

Ответ: 65