题目描述
Kenan 为沿着巴库大街某一侧的建筑和天桥绘制了一张规划图。规划图中有 n 栋建筑,从 0 到 n−1 编号。还有 m 座天桥,从 0 到 m−1 编号。这张规划图绘制在一张二维平面上,其中建筑和天桥分别是垂直和水平的线段。
第 i (0≤i≤n−1) 栋建筑的底部坐落在坐标 (x[i],0) 上,建筑的高度为 h[i]。因此,它对应一条连接点 (x[i],0) 和 (x[i],h[i]) 的线段。
第 j (0≤j≤m−1) 座天桥的两端分别在第 l[j] 栋建筑和第 r[j] 栋建筑上,并具有正的 y 坐标 y[j]。因此,它对应一条连接点 (x[l[j]],y[j]) 和 (x[r[j]],y[j]) 的线段。
称某座天桥和某栋建筑相交,如果它们有某个公共的点。因此,一座天桥在它的两个端点处与两栋建筑相交,同时还可能在中间和其他建筑相交。
Kenan 想要找出从第 s 栋建筑的底部到第 g 栋建筑的底部的最短路径长度,或者确认这样的路径不存在。在这里行人只能沿着建筑和天桥行走,并且不允许在地面上行走,也就是说不允许沿着 y 坐标为 0 的水平线行走。
行人能够在任意交点从某座天桥走进某栋建筑,或者从某栋建筑走上某座天桥。如果两座天桥的端点之一在同一点上,行人也可以从其中一座天桥走上另一座天桥。
你的任务是帮助 Kenan 回答他的问题。
输入格式
第一行,两个整数 n,m,表示建筑的栋数和天桥的座数。
以下 n 行,第 i (0≤i≤n−1) 行两个整数 x[i],h[i],表示第 i 栋建筑坐标和高度。
以下 m 行,第 j (0≤j≤m−1) 行三个整数 l[j],r[j],y[j],表示第 j 座天桥的左右端点和 y 坐标。
最后一行,两个整数 s,g,表示起点和终点。
输出格式
如果从第 s 栋建筑的底部到第 g 栋建筑的底部的最短路径存在,则该程序应该输出最短路径的长度。
否则,该程序应该输出 −1。
样例 1
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
27
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
21
数据范围与提示
对于所有数据:
- 1≤n,m≤105;
- 0≤x[0]<x[1]<⋯<x[n−1]≤109;
- 1≤h[i]≤109 (0≤i≤n−1);
- 0≤l[j]≤r[j]≤n−1 (0≤j≤m−1);
- 1≤y[j]≤min(h[l[j]],h[r[j]]) (0≤j≤m−1);
- 0≤s,g≤n−1;
- s=g;
- 除在端点处外,任意两座天桥不会有其他公共点。
详细子任务附加限制与分值如下表:
子任务编号 |
附加限制 |
分值 |
1 |
n,m≤50 |
10 |
2 |
每座天桥最多与 10 栋建筑相交 |
14 |
3 |
s=0,g=n−1,且所有的建筑的高度相等 |
15 |
4 |
s=0,g=n−1 |
18 |
5 |
没有任何附加限制 |
43 |