Question

На рисунке представлена схема дорог, соединяющих города А, Б, В, Г, Д, Е, Ж, И, К, Л. Каждая дорога имеет направление, указанное стрелкой. Требуется найти количество различных путей из города А в город Л.

Рисунок

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=105200)

Accepted Answer

24

Answer

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

Обозначим $N_X$ — количество различных путей из города А в город X.

Начнём с исходной вершины: $N_A = 1$.

Определим входящие рёбра для каждой вершины и вычислим количество путей:

- $N_Б = N_A = 1$
- $N_В = N_Б + N_А + N_Г = 1 + 1 + 1 = 3$
- $N_Г = N_A = 1$
- $N_Д = N_Е + N_В + N_Б = 3 + 3 + 1 = 7$
- $N_Е = N_В = 3$
- $N_Ж = N_Е + N_В + N_Г = 3 + 3 + 1 = 7$
- $N_И = N_Д = 7$
- $N_К = N_Ж = 7$

Финальный результат получаем, суммируя пути из всех вершин, из которых можно попасть в Л:

$$N_Л = N_И + N_Е + N_Ж + N_К = 7 + 3 + 7 + 7 = 24$$

Задание №13Компьютерные сети и системыЕГЭ по информатике