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

u9015471201

13 февраля 2017 г.

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

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

SOVA

13 февраля 2017 г.

★

Перепишем все пути, которые нам даны.
Из "А" можно попасть в "B" и "F".
Есть два варианта
"А–В" и "A–F"

Из "B" можно попасть в "C", "D", "Е".
"A–B–C", "A–B–D", "A–B–Е"
Из "C" можно попасть в "D".
Из "D" можно попасть в "F".
Из "E" можно попасть в "D","F".

Распишем все пути:
A – B – C – D – F ( 3 + 2 + 5 + 3+2 = 15)
A – B – D – E – F ( 3 + 3 + 3 + 2= 11)
A – B – E – F ( 3 + 7 + 2 = 12)
A – F (15)

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