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


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

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

 

ABCDEF
A41133
B44
C11471120
D713
E118
F3320138

 

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

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

В пункт F можно попасть из пунктов А, С, D, E.

В пункты Е и D можно попасть только пункта С.

В пункт С можно попасть из пунктов А и B.

В пункт В можно попасть из пункта А.

В пункты E и D можно попасть только из пункта С.

 

A-F. Длина маршрута 33.

 

A-C-F. Длина маршрута 11 + 20 =31.

 

A-С-E-F. Длина маршрута 11 + 11 + 8 = 30.

 

A-С-D-F. Длина маршрута 11 + 7 + 13 = 31.

 

Участок A-B-C может войти в три предыдущих пути, поэтому подставим его в самый короткий из них (A-С-E-F):

 

A-В-С-E-F. Длина маршрута 4 + 4 + 11 + 8 = 27.

 

Видно, что кратчайший путь равен 27.