#3180. 「IOI2019」天桥

内存限制:1024 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: alpha1022

题目描述

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

i\ (0 \le i \le n-1) 栋建筑的底部坐落在坐标 (x[i],0) 上,建筑的高度为 h[i] 。因此,它对应一条连接点 (x[i],0) (x[i],h[i]) 的线段。

j\ (0 \le j \le 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 \le i \le n-1) 行两个整数 x[i],h[i] ,表示第 i 栋建筑坐标和高度。
以下 m 行,第 j\ (0 \le j \le 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

样例输出 1

27

样例解释 1

Description

样例输入 2

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

样例输出 2

21

数据范围与提示

对于所有数据:

  • 1 \le n,m \le 10^5
  • 0 \le x[0] < x[1] < \dots < x[n-1] \le 10^9
  • 1 \le h[i] \le 10^9\ (0 \le i \le n-1)
  • 0 \le l[j] \le r[j] \le n-1\ (0 \le j \le m-1)
  • 1 \le y[j] \le \min(h[l[j]],h[r[j]])\ (0 \le j \le m-1)
  • 0 \le s,g \le n-1
  • s \ne g
  • 除在端点处外,任意两座天桥不会有其他公共点。

详细子任务附加限制与分值如下表:

子任务编号 附加限制 分值
1 n,m \le 50 10
2 每座天桥最多与 10 栋建筑相交 14
3 s = 0, g = n-1 ,且所有的建筑的高度相等 15
4 s = 0, g = n-1 18
5 没有任何附加限制 43