Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
Курьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе запишите натуральное число – длину минимального маршрута.
Курьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе запишите натуральное число – длину минимального маршрута.
More Questions From This User See All
Answers & Comments
Ответ:
22
Объяснение:
Строим граф - картинка 1
считаем пути
ABCDEZ = 4 + 3 + 11 + 4 + 1 = 23
ABCDFZ = 4 + 3 +11 + 3 + 2 = 23
ABCDEFZ = 4 + 3 + 11 + 4 + 4 + 2 = 28
ABCEFZ = 4 + 3 + 10 + 4 + 2 = 23
ABDEFZ = 4 + 8 + 4 + 4 + 2 = 22
ACDEFZ = 6 + 11 + 4 + 4 + 2 = 27
или
Строим дерево - картинка 2 (ветви, которые очевидно не достигают 6 пунктов не строим)
считаем пути