Question

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

Рисунок

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

Accepted Answer

16

Answer

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

Разобьём задачу на два этапа:
1. Найти количество путей из А в Г.
2. Найти количество путей из Г в М.
3. Перемножить результаты (так как любой путь из А в М через Г состоит из пути А → Г и пути Г → М).

Для каждого этапа применяем динамику: $f[v]$ — количество путей до вершины $v$ из стартовой вершины. Инициализируем $f[	ext{старт}] = 1$, затем для каждой вершины суммируем значения всех её предшественников.

**Этап 1: пути из А в Г**

Обходим граф в топологическом порядке, начиная с А:
- $f[A] = 1$
- Для каждой вершины $v$, достижимой из А, вычисляем $f[v] = \sum_{u 	o v} f[u]$

Получаем $f[Г]$ — количество путей из А в Г.

**Этап 2: пути из Г в М**

Аналогично, начиная с Г:
- $f[Г] = 1$
- Для каждой вершины $v$, достижимой из Г, вычисляем $f[v] = \sum_{u 	o v} f[u]$

Получаем $f[М]$ — количество путей из Г в М.

**Итоговый результат**

Количество путей из А в М через Г равно произведению:

$$	ext{Ответ} = f_1[Г] 	imes f_2[М]$$

где $f_1[Г]$ — пути из А в Г, $f_2[М]$ — пути из Г в М.

По графу на рисунке:
- Из А в Г: 2 пути
- Из Г в М: 8 путей
- Итого: $2 	imes 8 = 16$ путей

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

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