[BalticOI 2005] Bus Trip

这里有 $N$ 座城镇, 和城镇之间的 $M$ 巴士单行线(没有中间停靠站)。 城镇从$1$到 $N$ 标号。 一个旅行者在 $0$ 时刻位于 $1$ 号城镇想要到达 $P$ 号城镇。他将乘坐巴士在 $T$ 时刻到达 $P$ 号城镇。如果他早到了，他必须等待。 对于任意一个巴士路线 $i$ , 我们知道其中的起点城镇 $si$ 和目标城镇$ti$ 。我们也同样知道路线的出发时间和到达时间,但仅仅是近似值：我们知道巴士离开起点城镇 $si$ 在时间范围$[ai, bi]$内，且到达目标城镇 $ti$ 在时间范围$[ci, di]$内(端点值包括在内)。 旅行者不喜欢等待, 因此他要寻找一个旅行计划使得最大等待时间尽量小，同时保证绝对不会错过计划中的任何一辆巴士(意思是, 每次他换乘巴士, 他需要下车的巴士的最晚到达时间不会迟于他需要搭乘的下一辆巴士的最早出发时间)。 当计算等待时间时，我们必须假设最早可能到达的时间和最晚可能出发的时间。 编写一个程序，寻找一个最为合理的搭车计划。

输入文件名为TRIP.IN。第一行包含整数$N(1 \leq N \leq 50000),M(1 \leq M \leq 100000),P(1 \leq P \leq N),T(0 \leq T \leq 1000000000)$。 下面的M线描述了公交线路。每一行包含整数$si, ti, ai, bi, ci, di$，其中$si$和$ti$是公交线路$i$的始发地和目的地，$ai,bi,ci,di$描述了出发和到达时间，如上文所解释的$(1 \leq si \leq N, 1 \leq ti \leq N, 0 \leq ai \leq bi < ci \leq di \leq 1,000,000,000)$。

只需要包含一个数——最合理搭车方案的最长可能等待时间。如果不可能保证在 $T$ 时刻到达城市$P$，那么输出-1。

3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101

32

翻译来自BZOJ P1354