Question

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

Рисунок

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

Accepted Answer

6

Answer

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

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

Начинаем с вершины А (длина пути = 0). Затем последовательно вычисляем максимальные длины для остальных вершин, выбирая наибольшее значение среди всех входящих путей:

- **Б** = 1 (путь А → Б)
- **Г** = 1 (путь А → Г)
- **В** = 2 (путь А → Б → В)
- **Д** = 3 (путь А → Б → В → Д)
- **Ж** = 3 (путь А → Б → В → Ж)
- **Е** = 4 (путь А → Б → В → Д → Е)
- **И** = 4 (путь А → Б → В → Д → И)
- **К** = 5 (путь А → Б → В → Д → Е → К)
- **Л** = 6 (путь А → Б → В → Д → Е → К → Л)

Максимальная длина пути из А в Л составляет 6 рёбер.

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