На рисунке представлена схема дорог, связывающих города A, K, J, B, C, D, E, F, G, R, S, T, N, I, O, P, Q, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город M? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Заметим, что через середину идти совсем невыгодно, зачеркнём все дороги оттуда.
2. Также заметим дорогу LN, делающую левое направление более выгодным. Зачеркнём все дороги справа.
3. Зачеркнём OQ т.к. из O в Q выгоднее пройти через OP-PQ.
4. Зачеркнём LM т.к. из L в M выгоднее пройти через LN-NM.
Получаем путь AB-BE-EI-IO-OP-PQ-QL-LN-NM длиной 9.