Question

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

Рисунок

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

Accepted Answer

19

Answer

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

Используем принцип: количество путей до города X равно сумме количеств путей до всех городов, из которых есть прямая дорога в X.

Поскольку путь обязательно должен проходить через Л, разделим задачу на два этапа:
1. Найти количество путей из А в Л.
2. Найти количество путей из Л в М.
3. Перемножить результаты.

Однако проще вычислить количество путей до каждого города последовательно, учитывая, что для городов после Л мы берём только пути, идущие из Л (или его потомков).

Последовательный подсчёт:

- А = 1 (начальная вершина)
- Б = А = 1
- Д = А = 1
- Г = А + Д = 1 + 1 = 2
- В = Б + Г + А = 1 + 2 + 1 = 4
- Е = В + Б = 4 + 1 = 5
- З = Д = 1
- Ж = В + Г + Е + Д + З = 4 + 2 + 5 + 1 + 1 = 13
- И = Ж + Е + З = 13 + 5 + 1 = 19
- Л = И = 19 (количество путей из А в Л)
- К = И = 19
- М = Л = 19 (учитываем только пути через Л, поэтому К и И не включаем)

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

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