На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город J? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём HJ и IJ т.к. выгоднее пройти через HI-IK-KJ.
2. Зачеркнём FK т.к. выгоднее пройти через FH-HI-IK-KJ.
3. Зачеркнём BF, BG, GF т.к. выгоднее пройти через BC-CE-EF.
4. Зачеркнём AC т.к. выгоднее пройти через AB-BC или AD-DC.
5. Неважно, пойдём мы через D или через B.
Получаем путь AB-BC-CE-EF-FH-HI-IK-KJ длиной 8.
Ответ: 8
