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




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

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

 

ABCDEFG
A26
B253
C518
D63197
E95
F77
G857

 

Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.

Решение.

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

 

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

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

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

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

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

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

 

A−B−C−D−E−G. Длина маршрута 22.

 

A−B−C−D−F−G. Длина маршрута 22.

 

A−B−C−G. Длина маршрута 15.

 

A−B−D−E−G. Длина маршрута 19.

 

A−B−D−F−G. Длина маршрута 19.

 

A−D−F−G. Длина маршрута 20.

 

A−D−E−G. Длина маршрута 20.

 

A−B−D−С−G. Длина маршрута 14.

 

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

 

Ответ: 14.