Задача №524. Рейсы во времени
Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.
В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте B как можно раньше (то есть в наименьший возможный момент времени).
При этом разрешается делать пересадки с одного рейса на другой. Если вы прибываете в некоторый пункт в момент времени \(T\), то вы можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени \(T\) или позднее (но не раньше).
В первой строке вводится число \(N\) – количество населенных пунктов ( 1\( \le\)N\( \le\)1000). Вторая строка содержит два числа \(A\) и \(B\) – номера начального и конечного пунктов. В третьей строке задается \(K\) – количество рейсов ( 0\( \le\)K\( \le\)1000). Следующие \(K\) строк содержат описания рейсов, по одному на строке. Каждое описание представляет собой четверку целых чисел. Первое число каждой четверки задает номер пункта отправления, второе – время отправления, третье – пункт назначения, четвертое – время прибытия. Номера пунктов – натуральные числа из диапазона от 1 до \(N\). Пункт назначения и пункт отправления могут совпадать. Время измеряется в некоторых абсолютных единицах и задается целым числом, по модулю не превышающим \(10^9\). Поскольку рейсы совершаются на машинах времени, то время прибытия может быть как больше времени отправления, так и меньше, или равным ему.
Гарантируется, что входные данные таковы, что добраться из пункта \(A\) в пункт \(B\) всегда можно.
Выведите минимальное время, когда вы сможете оказаться в пункте \(B\).
2 1 1 2 1 1 2 10 1 10 1 9
0
1 1 1 3 1 3 1 -5 1 -5 1 -3 1 -4 1 -10
-10
5 1 2 6 1 0 3 10 4 2 2 -10 4 14 2 -7 3 10 2 10 2 0 4 2 3 10 4 12
-10