Question

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

Answer 1

Ответ:

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 пунктов не строим)

считаем пути