На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, O, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Через какое количество городов проходит самая длинная дорога из города А в город Т (включая город А и Т)?
Уничтожаем короткие маршруты. Уничтожим АГ, так АБГ длинее. Уничтожим ДЗ, так как ДГЕЗ длинее. Уничтожим ГЖ, так как ГЕЖ длиннее. Уничтожим ЕЗ, так как ЕЖЗ длиннее. Уничтожим БВ, так как БГВ длиннее. Уничтожим ГЕЖ, так как ГВЖ такой же. Уничтожим ВИ, так как ВЖИ короче. Уничтожим ЖК и ЖЛ, так как ЖИК длиннее. Уничтожим ЖЗЛ, так так ЖИКЛ больше. КО, ИО, ИМ — короткие маршруты, лучше идти в обход. Уничтожаем ОН, так как ОМН длиннее. МТ — короткий маршрут, лучше МНТ. Остается: АБГВЖИКЛОМНТ.