Ко­ли­че­ство путей до го­ро­да Х = ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

При этом если путь дол­жен не про­хо­дить через какой-то город, нужно про­сто не учи­ты­вать этот город при подсчёте сумм. А если город на­о­бо­рот обя­за­тель­но дол­жен ле­жать на пути, тогда для го­ро­дов, в ко­то­рые из нуж­но­го го­ро­да идут до­ро­ги, в сум­мах нужно брать толь­ко этот город.

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1

Б = 1 = 1

В = А = 1

Д = Б = 1

Г = А + Б + Д = 3

И = Г = 3 (В не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

Е = Г + И = 6 (Д и Ж не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

К = Е + И = 9

Л = Е = 6 (Ж и Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

М = К + Л = 15

П = Л + М = 21 (Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

При­ме­ча­ние. Не­об­хо­ди­мо найти ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город П, про­хо­дя­щих через город Г.

Ответ: 21.