Оптимизация маршрута —Каталог задач по ЕГЭ - Информатика

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

Задача 1#6707

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

$PIC$

Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Показать ответ и решение

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

Маршрут B—D—E, длина 11 км.

Маршрут B—C—D—E, длина 10 км.

Маршрут B—С—D—A—E, длина 9 км.

Любые другие маршруты будут длиннее маршрута B—С—D—A—E. Самый короткий путь: B—С—D—A—E. Длина маршрута 9 км.

Ответ: 9

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

Задача 2#6705

На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.

Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами. $PIC$

Показать ответ и решение

Заметим, что наиболее удалены друг от друга пункты A и D. Найдём все варианты маршрутов из A в D и выберем самый короткий.

A—B—D: длина маршрута 13 км.

A—C—D: длина маршрута 15 км.

A—B—C—D: длина маршрута 23 км.

A—C—B—D: длина маршрута 17 км.

Заметим, что кратчайшее расстояние между пунктами A и D равняется 13.

Ответ: 13

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

Задача 3#6585

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

$PIC$

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

Показать ответ и решение

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

$PIC$

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

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

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

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

Ответ: 9

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

Задача 4#6584

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

$PIC$

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

Показать ответ и решение

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

$PIC$

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

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

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

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

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

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

Ответ: 81

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

Задача 5#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

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

Задача 6#6452

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых в километрах приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

$PIC$

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.

Показать ответ и решение

Для удобства представим таблицу в виде графа:

$PIC$

Прямой путь из A в F = 11. Путь из A в В, как видим, никуда не ведет, поэтому его не рассматриваем. Рассмотрим все остальные пути.

Если пойдем в С, пути будут такие:

1) $A − C − F = 8$ ;

2) $A − C − D − F = 9$ ;

3) $A − C − D − E − F = 19$ .

Если пойдем в D:

1) $A − D − F = 9$ ;

2) $A − D − C − F = 12$ ;

3) $A − D − E − F = 19$ .

Если пойдем в E:

1) $A − E − F = 10$ ;

2) $A − E − D − F = 6$ ;

3) $A − E − D − C − F = 9$ .

Видим, что кратчайший путь = 6.

Ответ: 6

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

Задача 7#6451

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

$PIC$

Определите длину кратчайшего пути между пунктами А и G (при условии, что передвигаться можно только по построенным дорогам).

Показать ответ и решение

Для удобства представим таблицу в виде графа:

$PIC$

Прямой путь из A в G – 25, из A в C самый короткий путь – через B (прямой = 9, через B – 4 + 3 = 7), C-F-G = 13 + 1 = 14, прямой путь из C в G = 20 > 14, C-D-E-G = 2 + 4 + 4 = 10 < 14, то есть из C кратчайший путь в G = 10, а кратчайший путь в C = 7, то есть весь путь из A в G = 7 + 10 = 17 < 25 (прямой путь из A в G). Тогда наш ответ – 17.

Ответ: 17

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

Задача 8#6450

Между населёнными пунктами А, В, С, D, Е, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

$PIC$

Определите длину кратчайшего пути между пунктами А и G (при условии, что передвигаться можно только по построенным дорогам).

Показать ответ и решение

Для удобства представим таблицу в виде графа:

$PIC$

Прямой путь A-G = 34. Из А также можем попасть в B, D, C.

Из B в D можно попасть напрямую – длина 6, через С – длина 4 + 2 = 6, то есть из A через B в D – 4 + 6 = 10. Из A в D – напрямую за 15 или через C: 10 + 2 = 12. Тогда из A в D можно попасть по пути длиной 10.

Из D в G – по пути длиной 15 напрямую или через E и F. D-E-G = 3 + 9 = 12, D-E-F-G = 3 + 8 + 4 = 15, D-F-G = 11 + 4 = 15. То есть кратчайший путь из D в G – длиной 12. Тогда кратчайший путь из A в G = 10 + 12 = 22.

Ответ: 22