Задача 7408 Между населёнными пунктами А, В, С, D,...

YanMarkov

04.03.2016

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

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

Перепишем все пути, которые нам даны.
Из 'А' можно попасть в 'B' и 'E'.
Из 'B' можно попасть в 'C', 'D' и 'E'.
Из 'C' можно попасть в 'E'.
Из 'D' можно попасть в 'E'.
Из 'E' можно попасть в 'F'.

Перебираем пути:
A - B - C - E - F | 3 + 7 + 2 + 7 = 19
A - B - D - E - F | 3 + 4 + 6 + 7 = 20
A - B - E - F | 3 + 11 + 7 = 21
A - E - F | 29 + 7 = 36

Длина самого короткого пути равна 19.

Ответ: 19