Шешімі: Пути через заданный город
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город В?
Шешім по шагам
3 қадамРассмотрим только пути, проходящие через город В. Каждый такой путь однозначно состоит из пути из А в В и пути из В в М.
$$N = N_{A\to В}\cdot N_{В\to M}$$Для подсчёта количества путей используем динамический подсчёт: число путей в вершину равно сумме чисел путей в вершины, из которых в неё ведут стрелки.
После подсчёта путей от А до В и от В до М перемножаем полученные значения.
$$N = 24$$Где здесь ошибаются
Считать все пути из А в М, не исключая пути, которые не проходят через В.
Складывать количество путей из А в В и из В в М вместо умножения.
Игнорировать направление стрелок на дорогах.