ЕГЭ и ОГЭ
Главная > 2017: ЕГЭ, ОГЭ Математика, Физика, ... > ЕГЭ 2017. Информатика. В.Р. Лещинер. 10 вариантов. Типовые тестовые задания.

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

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

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

Решение.

По данным таблицы построим граф связи пунктов между собой. При этом вес ветвей графа будет соответствовать расстоянию между пунктами, которые они соединяют (см. рисунок ниже).

Из рисунка видно, что кратчайшее расстояние между пунктами A и F – это маршрут ABCEF с длиной 4+3+7+6=20.

Ответ: 20.

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

Темы раздела