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


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

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

 

 

АБВГДЕК
А5
Б5358
В34
Г513
Д84125
Е21
К351

 

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

Решение.

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут А—Б—В—Д—Г—К, его длина равна 16 км. Теперь, начиная с конца маршрута, будем изменять населённые пункты:

 

А—Б—В—Д—Е—К: длина маршрута 15 км,

A—Б—Г—Д—Е—К: длина маршрута 14 км.

A—Б—Г—К: длина маршрута 13 км.

 

Дальнейшее изменение населённых пунктов, через которые проходит маршрут, бессмысленно, поскольку длины маршрутов будут более 13 км. Следовательно, длина кратчайшего маршрута равна 13 км.

 

Ответ: 13.

Источник: ЕГЭ по ин­фор­ма­ти­ке 23.03.2016. До­сроч­ная волна