UOJ Logo Universal Online Judge

UOJ

#538. 【IOI2019】天桥

附件下载 统计

Kenan 为沿着巴库大街某一侧的建筑和天桥绘制了一张规划图。规划图中有 n 栋建筑,从 0n1 编号。还有 m 座天桥,从 0m1 编号。这张规划图绘制在一张二维平面上,其中建筑和天桥分别是垂直和水平的线段。

i 栋建筑的底部坐落在坐标 (xi,0) 上,建筑的高度为 hi 。因此,它对应一条连接点 (xi,0)(xi,hi) 的线段。

i 座天桥的两端分别在第 li 栋建筑和第 ri 栋建筑上 (liri),并具有正的 yi 坐标 。因此,它对应一条连接点 (xli,yi)(xri,yi) 的线段。

称某座天桥和某栋建筑相交,如果它们有某个公共的点。因此,一座天桥在它的两个端点处与两栋建筑相交,同时还可能在中间和其他建筑相交。

Kenan 想要找出从第 s 栋建筑的底部到第 g 栋建筑的底部的最短路径长度,或者确认这样的路径不存在。在这里行人只能沿着建筑和天桥行走,并且不允许在地面上行走,也就是说不允许沿着 y 坐标为 0 的水平线行走。

行人能够在任意交点从某座天桥走进某栋建筑,或者从某栋建筑走上某座天桥。如果两座天桥的端点之一在同一点上,行人也可以从其中一座天桥走上另一座天桥。

你的任务是帮助 Kenan 回答他的问题。

输入格式

第一行两个整数 n,m,表示建筑的栋数和天桥的座数。

以下 n 行,第 i 行两个整数 xi1,hi1,表示第 i1 栋建筑坐标和高度。

以下 m 行,第 i 行三个整数 li1,ri1,yi1,表示第 i1 座天桥的左右端点和 y 坐标。

最后一行,两个整数 s,g,表示起点和终点。

输出格式

如果不存在一条合法的从 s 的底部到 g 的底部的路径,输出1

否则输出所有路径中长度最短的那一条。

样例一

plain

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

output

27

explanation

样例一示意图

样例二

plain

5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4

output

21

数据范围

测试包编号限制与约定分值
1n,m5010
2每座天桥至多与10座建筑相交14
3s=0,g=n1,且所有建筑高度相等15
4s=0,g=n118
5无特殊约定43

对于所有测试数据,满足 1n,m100000,0xi109,1hi109

对于所有测试数据,满足 0li<rin1,0yimin(hli,hri),xixi+1

保证所有天桥仅可能在端点处相交。

时间限制: 4s

空间限制: 1GB