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

YanMarkov

13.03.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