Задание EGEINF57BDEB: Графы, таблицы и маршруты

Решение.
Длина пути по условию — число пройденных дорог. Нужен самый длинный путь, поэтому при объединении вариантов берём максимум длин, а не складываем количества маршрутов.
Обозначим L(X) наибольшую длину пути от А до города X. Положим L(А) = 0: в начале ещё не пройдено ни одной дороги.
Города можно обработать в порядке А, Б, Д, Е, Г, З, В, Ж, И, К, Л, М. На рисунке каждая стрелка ведёт от более раннего города этого списка к более позднему. Следовательно, циклов нет, а при обработке города все его предшественники уже рассмотрены.
Любой путь в X заканчивается одной из входящих дорог Y → X. Эта последняя дорога прибавляет 1 к длине пути в Y. Поэтому L(X) = 1 + max L(Y), где рассматриваем все города Y с прямой дорогой в X. Это учитывает каждый возможный последний шаг.
L(Б) = 1 + L(А) = 1 + 0 = 1.
L(Д) = 1 + L(А) = 1 + 0 = 1.
L(Е) = 1 + L(Б) = 1 + 1 = 2.
L(Г) = 1 + max(L(А), L(Д)) = 1 + max(0, 1) = 2.
L(З) = 1 + L(Д) = 1 + 1 = 2.
L(В) = 1 + max(L(А), L(Б), L(Г)) = 1 + max(0, 1, 2) = 3.
L(Ж) = 1 + max(L(В), L(Г), L(Д), L(Е), L(З)) = 1 + max(3, 2, 1, 2, 2) = 4.
L(И) = 1 + max(L(Е), L(Ж), L(З)) = 1 + max(2, 4, 2) = 5.
L(К) = 1 + L(И) = 1 + 5 = 6.
L(Л) = 1 + L(И) = 1 + 5 = 6.
L(М) = 1 + max(L(И), L(К), L(Л)) = 1 + max(5, 6, 6) = 7.
Получили L(М) = 7. Эта оценка достижима: А → Д → Г → В → Ж → И → К → М.
Проверка: в указанной последовательности 8 городов и 7 дорог между соседними городами. Все нужные стрелки присутствуют на рисунке, повторных посещений нет.
Более длинного пути быть не может: в каждом городе сравнили все входящие дороги и взяли максимальное достижимое значение. Поэтому вычисление даёт одновременно верхнюю границу длины и маршрут, достигающий её.
Ответ: 7.