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


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

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

 

ABCDEFZ
A4921
B43
C9321120
D24
E44
F112
Z212042

 

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

Решение.

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

 

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

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

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

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

В пункт F можно попасть из пунктов C, Z.

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

 

Длина маршрута A-Z равна 21.

 

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

 

Длина маршрута A-C-Z равна 9 + 20 = 29.

 

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

 

Длина маршрута A-C-F-Z равна 9 + 11 + 2 = 22.

 

Длина маршрута A-B-C-F-Z равна 4+3+11+2 = 20,

 

Кратчайший путь равен 17.