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

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

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

А = 1

Б = А = 1

Г = А + Б = 1 + 1 = 2 (т. к. про­хо­дить через город нужно Г обя­за­тель­но)

Д = Г = 2

Ж = Г + Д = 4 (т. к. нель­зя про­хо­дить через город З)

И = Д = 2

К = Ж + Д + И = 8

Ответ: 8.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город К, про­хо­дя­щих через город Г, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Г и ко­ли­че­ства путей из го­ро­да Г в город К.

Из го­ро­да А в город Г есть 2 пути: А—Г и А—Б—Г.

Най­дем ко­ли­че­ство путей из го­ро­да Г в город К (при этом Г - ис­ход­ный пункт). По усло­вию, эти пути не долж­ны про­хо­дить через город З.

Г = 1

Д = Г = 1

Ж = Г + Д = 2

И = Д = 1

К = Ж + Д + И = 4.

Таким об­ра­зом, ко­ли­че­ство путей из го­ро­да А в город К, про­хо­дя­щих через город Г и не про­хо­дя­щих через город З, равно 2 · 4  =  8.