На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, H, K, I, J, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город G? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
Рисунок симметричен, можно рассматривать только верхнюю или только нижнюю его часть. Возьмём верхнюю.
1. Зачеркнём BJ т.к. выгоднее пройти через BD-DJ.
2. Зачеркнём JE т.к. выгоднее пройти через JK-KE.
Получаем путь AB-BD-DJ-JK-KE-EG длиной 6.
Ответ: 6