Поиск количества путей в ориентированном графе (страница 2)

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Итого получается, что в пункт I ведут 17 различных путей.

Ответ: 17

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт F ведут 11 различных путей.

Ответ: 11

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт I ведут 27 различных путей.

Ответ: 27

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт K ведут 37 различных путей.

Ответ: 37

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт D ведут 22 различных пути.

Ответ: 22

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт L ведут 104 различных пути.

Ответ: 104

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт J ведут 40 различных путей.

Ответ: 40