** схеме нарисованы дороги между населенными пунктами A, B, C, D, E, F и указаны...

0 голосов
82 просмотров

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


image

Информатика (56 баллов) | 82 просмотров
Дан 1 ответ
0 голосов

Кратчайший из A-F через:
A-D-F = 5

(56 баллов)
0

уже битый час сижу и не могу понять как вы это считаете.

0

Рисую "дерево". Начинаю от А, далее от нее ответвления В, С, D и т.д, чтобы они попали в F. Пошагово считаю сколько единиц на той или иной дороге. Кратчайшая дорога(самая маленькая сумма) - это и есть ответ.