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

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