На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Определите количество путей из пункта А до пункта К, проходящих через Ж, но не проходящих через В.
Прежде всего отметим пункт В числом 0. Затем найдём количество путей до пункта Ж. Пути, которые до Ж не доводят, мы не считаем и не отмечаем.
После этого оставляем только вес вершины Ж. Остальные веса меняем на 0. Пункты, которые не ведут в Ж, по-прежнему не трогаем.
Дороги по схеме: А→Б, А→В, А→Г, В→Б, В→Г, Б→Д, Д→Е, Д→Ж, Е→Ж, Е→З, Ж→З, Ж→И, Г→И, З→К, И→К.
Шаг
В Ж ведут только Д и Е, поэтому Г и И не отмечаем.
Вес вершины равен сумме весов вершин, из которых в неё входят дороги.
До Ж ведут
Шаг
Считаем дальше только пути, прошедшие через Ж:
Чтобы посчитать пути через нужную вершину, сначала находят число путей до неё, а затем обнуляют остальные веса и считаем дальше. Запрещённую вершину отмечают нулём.
Шаг
