Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость

Question

Информатика: Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет. Курьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе

ZiGZaG4242 · Answer

22Объяснение:Строим граф - картинка 1считаем путиABCDEZ = 4 + 3 + 11 + 4 + 1 = 23ABCDFZ = 4 + 3 +11 + 3 + 2 = 23ABCDEFZ = 4 + 3 + 11 + 4 + 4 + 2 = 28ABCEFZ = 4 + 3 + 10 + 4 + 2 = 23ABDEFZ = 4 + 8 + 4 + 4 + 2 = 22ACDEFZ = 6 + 11 + 4 + 4 + 2 = 27 илиСтроим дерево - картинка 2 (ветви, которые очевидно не достигают 6 пунктов не строим)считаем пути...

Популярные вопросы