СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
Информатика
Cайты, меню, вход, новости


Задания
Версия для печати и копирования в MS Word
Задание 3 № 7442

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

 

ABCDEFG
A51225
B58
C24510
D1282
E45
F55
G251055

 

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

Решение.

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—C—E—G, его длина равна 24 км. Теперь, начиная с конца маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, C—E—G больше расстояния C—G, то заменяем участок маршрута C—E—G на C—G.

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

Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.

Ответ: 23 км.

Источник: Демонстрационная версия ЕГЭ—2015 по информатике.