Задание:
Между населенными пунктам A,B,C,D,E,F,Z построены дороги протяженность которых приведена в таблице (отсутствие числа в таблице означает, что прямойдороги между пунктами нет)
Решение:
1) Из А только два пути — AB=7, AZ=57.AZ слишком большой, для начала отбросим его. Идем по AB=7. 2) Из B три пути: BC=5, BD=7, BE=27.BE слишком большой, пока отбросим его.2,1) Рассмотрим для BC=5: Из C есть только один путь, CD=3. Рассмотрим для CD: Из D есть DB, но нам незачем возвращаться; значит остается DE=2. Рассмотрим для DE: Из Е есть EB, но это возврат, есть EF=2 и EZ=82,1,1) Если мы идем по EF, то от F есть FZ=3В итоге, получается: A-B-C-D-E-F-Z=7+5+3+2+2+3=222,1,2) Если в предпоследнем шаге пойти по EZ=8, то получается A-B-C-D-E-Z=7+5+3+2+8=25 2,2) Рассмотрим для BD=7Этим шагом мы как бы перескочим B-C-DИз D есть DC и DE, идти в С нет смысла, так что идем в DE=2Из Е есть EF=2 и EZ=82,2,1) Для начала пойдем в EF=2, FZ=3Получается A-B-D-E-F-Z=7+7+2+2+3=21 2,2.2) Другой вариант, EZ=8Получается A-B-D-E-Z=7+7+2+8=24 Ответ уже найдет, выделен жирным, но в других задачах иногда нужно просмотреть абсолютно все пути.
Знаете другой ответ?