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

YanMarkov

13 марта 2016 г.

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

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

Распишем все пути:
A – B – C – D – F | 4 + 3 + 3 + 12 = 22
A – B – C – E – F | 4 + 3 + 7 + 6 = 20
A – B – C – F | 4 + 3 + 14 = 21
A – C – D – F | 10 + 3 + 12 = 25
A – C – E – F | 10 + 7 + 6 = 23
A – C – F | 10 + 14 = 24
A – F | 24

Самый короткий путь: ABCEF – 20.

Ответ: 20