На рисунке представлена схема дорог, связывающих города A, I, B, C, D, F, G, E, H, J, K, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город Q? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём AC т.к. из A в C выгоднее пройти через AD-DC или через AB-BC.
2. Мы можем пойти через верхний, через нижний или через средний путь и везде встретим одну и ту же конструкцию, но из-за выгоды в пункте 1 средний путь более привлекателен, так как, чтобы добраться до него, нужно преодолеть ещё одну дорогу.
3. Зачеркнём CJ, JO, CI, HO т.к. из C в O выгоднее пройти через CH-HI-IO.
Получаем путь AB-BC-CH-HI-IO-OQ длиной 6.