Вам даны задача и её решение — верное, но не удовлетворяющее заданным ограничениям на время работы. Переработайте это решение и сдайте в систему.
Разработайте простейшую систему маршрутизации экспрессов, курсирующих по одному железнодорожному направлению, представляющему собой прямую. Ваша программа должна уметь обрабатывать запросы двух типов:
- ADD start finish — добавить в систему маршрутов экспресс, следующий со станции start до станции finish и обратно. Экспресс не делает промежуточных остановок. Станции задаются целыми числами, равными их расстоянию от вокзала (он имеет номер 0).
- GO start finish — попытаться проложить беспересадочный маршрут от станции start до станции finish. Если существует экспресс между этими двумя станциями, в ответ на данный запрос выведите 0. В противном случае выведите положительное число — минимальное расстояние, на которое можно приблизиться к станции finish, стартовав строго на станции start и использовав не более одного экспресса.
В первой строке вводится количество запросов Q — натуральное число, не превосходящее
Для каждого запроса GO выведите единственное целое неотрицательное число — минимальное расстояние до конечной станции маршрута, вычисляемое в соответствии с описанными выше правилами.
1 секунда на выполнение всех запросов. Все описанные в условии гарантии действительно справедливы для всех тестов, на которых будет запускаться ваша программа. Проверять корректность тестов не нужно.
Ввод 7 ADD -2 5 ADD 10 4 ADD 5 8 GO 4 10 GO 4 -2 GO 5 0 GO 5 100
Вывод 0 6 2 92
В первом запросе GO выгодно воспользоваться экспрессом 10 4. Во втором выгоднее остаться на месте, чем пользоваться экспрессом. В третьем и четвёртом запросах GO необходимо воспользоваться экспрессами -2 5 и 5 8.