Question

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

Рисунок

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

Accepted Answer

96

Answer

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

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

Последовательно вычислим количество путей:

**Этап 1. Пути от А до Л:**

- А = 1 (начальная вершина)
- Б = А = 1
- Г = А + Б = 2
- Д = А = 1
- В = Б + Г = 3
- Е = Г + Д = 3
- Ж = В + Г + Е = 8
- К = Ж = 8
- Л = Ж + К = 16

**Этап 2. Пути от Л до Т (учитываем только пути через Л):**

Для городов, в которые ведут дороги из Л, берём только значение Л:

- М = Л = 16 (не учитываем Ж и Н, так как путь должен проходить через Л)
- П = Л + М = 32 (не учитываем К, так как путь должен проходить через Л)
- Р = П = 32
- С = П = 32
- Т = Р + С + П = 96

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