на рисунке схема дорог ,которые связывают города а,б,в,г,д,е,з,ж,и и к по каждой дороге можно двигаться только в одном направлении,указанном стрелкой.сколько путей ведут из города…

Не могу ответить точно без самой схемы дорог. Пришлите изображение или дайте перечень ребер (какие города связаны стрелками). Тогда посчитаю точное количество путей из а в к, проходящих через д и в.

А пока как можно посчитать это в общем случае:

Вариант 1. Путь должен проходить через д и в в любом порядке (есть или нет последовательность д→в или в→д в конкретном пути).

• Постройте граф как ориентированный граф без циклов (обычно в таких задачах граф DAG).
• Используйте динамическое программирование по состояниям посещения двух городов:
  • Пусть a — старт, k — цель, d — город Д, v — город В.
  • DP[u][mask] — число путей от a до города u, где mask
    • бит 0 (1) = посещён город d,
    • бит 1 (2) = посещён город v.
  • Инициализация: DP[a][0] = 1.
  • Для каждого ребра u → w обновляйте: новый_mask = mask | (w==d?1:0) | (w==v?2:0); DP[w][new_mask] += DP[u][mask].
  • Пройдите вершины в топологическом порядке (или используйте обход по DAG).
  • Ответ: DP[k][3] (то есть путей, дошедших до к и посетивших оба города d и v).

Этот подход корректно считает пути через оба города (независимо от порядка посещения). Замечание: если в графе есть циклы и считать нужно только простые пути, то такой DP даст бесконечное число или потребует специальной обработки (по условию задачи обычно граф DAG).

Вариант 2. Если порядок обязателен: сначала д, потом в, потом к.

• Тогда можно посчитать N(a→d), N(d→v) и N(v→k) — количества путей по DAG между соответствующими парам вершин.
• Тогда число путей через d и потом через v равно N(a→d) · N(d→v) · N(v→k).
• Обратите внимание, что это верно в случае, что при таких путях нет перекрытий с повторениями вершин (что гарантируется отсутствием циклов в DAG).

Пожалуйста, пришлите схему (edges), и скажите, какой вариант вы считаете: через d и v в любом порядке или строго д→v. Я быстро дам точное число.