Question

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

Рисунок

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

Accepted Answer

60

Answer

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

**Первый способ — прямой подсчёт с ограничением:**

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

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

- A = 1
- Б = A = 1
- Д = A = 1
- Г = A + Д = 2
- В = A + Б + Г = 4

После города В учитываем только пути, исходящие из В:

- Е = В = 4
- З = В = 4
- Ж = В + Е + З = 12
- И = Е + Ж + З = 20
- К = И = 20
- Л = И = 20
- М = К + И + Л = 60

**Второй способ — произведение путей:**

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

Пути из А в В:
- A = 1
- Б = 1
- Д = 1
- Г = 2
- В = 4

Пути из В в М (заметим, что все они проходят через И):

Из В в И:
- В = 1
- Е = 1
- З = 1
- Ж = 3
- И = 5

Из И в М: три пути (И→К→М, И→Л→М, И→М).

Итого: 4 × 5 × 3 = 60.

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