ЕГЭ и ОГЭ
Главная

Источник задания: Решение 2538. ЕГЭ 2017. Информатика. В.Р. Лещинер. 10 вариантов.

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

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

Решение.

Ниже на рисунке представлен граф расстояний между точками пунктов. Дуги этого графа пронумерованы в соответствии с расстояниями между соответствующими пунктами.

Из графа видно, что минимальное расстояние от A до Z соответствует маршруту ACDZ с расстоянием 7+6+14=27.

Ответ: 27.

Другие задания:

Темы раздела

Для наших пользователей досутпны следующие материалы: