Question

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

Рисунок

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

Accepted Answer

23

Answer

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

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

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

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

$N_В = N_А = 1$

$N_Б = N_А + N_В = 1 + 1 = 2$

$N_Г = N_В + N_А = 1 + 1 = 2$

$N_Д = N_Б + N_В = 2 + 1 = 3$

$N_Е = N_Д + N_В + N_Ж$

$N_Ж = N_В + N_Г = 1 + 2 = 3$

Подставим $N_Ж$ в формулу для $N_Е$:

$N_Е = 3 + 1 + 3 = 7$

$N_И = N_Д + N_Е = 3 + 7 = 10$

$N_К = N_Ж = 3$

Наконец, вычислим количество путей в финальную вершину:

$N_Л = N_И + N_Е + N_Ж + N_К = 10 + 7 + 3 + 3 = 23$

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