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


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

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

 

ABCDEFZ
A4101534
B446
C1042
D156231115
E389
F1184
Z341594

 

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

Решение.

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

 

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

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

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

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

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

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

 

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

 

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

 

A-D-Z: Длина маршрута 30 км.

 

A-D-F-Z: Длина маршрута 30 км.

 

A-D-E-Z: Длина маршрута 27 км.

 

A-D-E-F-Z: Длина маршрута 30 км.

 

A-B-D-Z: Длина маршрута 25 км.

 

A-B-D-F-Z: Длина маршрута 25 км.

 

A-B-D-E-Z: Длина маршрута 22 км.

 

A-B-D-E-F-Z: Длина маршрута 25 км.

 

A-B-C-D-Z: Длина маршрута 25 км.

 

A-B-C-D-E-Z: Длина маршрута 22 км.

 

A-B-C-D-F-Z: Длина маршрута 25 км.

 

A-B-C-D-E-F-Z: Длина маршрута 25 км.

 

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