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


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

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

 

ABCDEFZ
A4823
B43
C83281120
D24
E844
F112
Z232042

 

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

Решение.

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

 

Из пункта A можно попасть в пункты B, C и Z.

Из пункта B можно попасть в пункт C.

Из пункта C можно попасть в пункты D, E, F и Z.

Из пункта D можно попасть в пункт E.

Из пункта E можно попасть в пункт Z.

Из пункта F можно попасть в пункт Z.

 

Путь A-B-С — 7км, а A-С — 8км. Следовательно, варианты, начинающиеся через пункт С не рассматриваем.

 

A-Z. Длина маршрута 23км

 

A-B-C-D-E-Z. Длина маршрута 7+2+4+4=17.

 

A-B-C-E-Z. Длина маршрута 7+8+4=19.

 

A-B-C-F-Z. Длина маршрута 7+11+2=20.

 

A-B-C-Z. Длина маршрута 7+20=27.

 

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