Задание №37522 ЕГЭ Информатике

Начнём строить возможные маршруты из пункта A.

За 1 шаг можно приехать в B, D или сразу в G (в скобках показаны длины маршрутов):

 

AB (5), AD (12), AG (25)

 

Заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25.

Строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен):

 

ABD (5 + 8 = 13)

 

Этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12.

Из D можно ехать в B и C:

 

         ADB (12 + 8 = 20)

         ADC (12 + 2 = 14)

 

Третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D.

Продолжаем маршрут ADC (14):

 

ADCE (14 + 4 = 18)

ADCF (14 + 5 = 19)

ADCG (14 + 10 = 24)

 

В последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее.

Четвёртый шаг: продолжаем маршрут ADCE:

 

ADCEG (18 + 5 = 23)

 

и маршрут ADCF:

 

ADCFG (19 + 5 = 24)

 

Других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.