注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "plain.h"。

题目描述

题目译自 2019년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T4 「대평원」

一只蚂蚁在大平原上从起点移动到终点，它以每公里 $100$ 分钟的速度前进。蚂蚁只能平行于 $x$ 轴和 $y$ 轴移动，在丘陵地带移动时间可能会增加。给定起点、终点、丘陵地带的范围和每个丘陵地带 $1$ 公里的移动时间，计算蚂蚁从起点到终点所需的最短时间。

丘陵地带是由平行于 $x$ 轴和 $y$ 轴的边组成的矩形，每个矩形都有 $1$ 公里的移动时间。这段时间只适用于矩形的内部，不适用于边界。此外，不同的矩形不会重叠，起点、终点和不同的矩形的顶点坐标都是整数且不重叠。起点和终点始终位于所有矩形的外部。

例如，下图显示了两个矩形，其中一个矩形的左下角坐标为 $(0,1)$，右上角坐标为 $(5,2)$，每公里移动时间为 $200$ 分钟。另一个矩形的左下角坐标为 $(4,3)$，右上角坐标为 $(9,4)$，每公里移动时间为 $1000$ 分钟。图中标注了从点 $A$ 到点 $B$ 以及从点 $C$ 到点 $D$ 的最短时间路径，它们分别为 $700$ 分钟和 $1000$ 分钟。

你需要实现以下函数：

• long long shortest_path(pair<int, int> src, pair<int, int> dst, vector<pair<int, int>> p1, vector<pair<int, int>> p2, vector<int> w);
  这个函数只会调用一次。src 和 dst 分别是起点和终点。每个矩形的左下角坐标在 p1，右上角坐标在 p2。利用给定的值计算从 src 到 dst 的最短时间并返回。

实现细节

你需要提交一个名为 plain.cpp 的文件。该文件必须实现以下函数：

long long shortest_path(pair<int, int> src, pair<int, int> dst, vector<pair<int, int>> p1, vector<pair<int, int>> p2, vector<int> w);

函数必须按照上述描述进行操作。当然，你可以创建和使用其他函数，但不得进行任何输入输出操作或访问其他文件。

示例评测程序

示例评测程序按以下格式读取输入。$x, y$ 坐标的单位为公里：

• 第 $1$ 行：$N\,x_{s}\,y_{s}\,x_{e}\,y_{e}$，其中 $N$ 表示矩形的数量，$x_{s}, y_{s}$ 表示起点的 $x$ 和 $y$ 坐标，$x_{e}, y_{e}$ 表示终点的 $x$ 和 $y$ 坐标
• 接下来的 $N$ 行：每行给出一个矩形的坐标和移动时间 $x_{1}\,y_{1}\,x_{2}\,y_{2}\,w$，其中 $x_{1}, y_{1}$ 表示矩形左下角的 $x$ 和 $y$ 坐标，$x_{2},y_{2}$ 表示矩形右上角的 $x$ 和 $y$ 坐标，$w$ 表示矩形内部的 $1$ 公里移动时间

示例评测程序会输出 shortest_path 函数的返回值。

3 2 14 5 1
4 6 6 10 1000
0 7 3 9 200
1 2 8 5 150

1750

13 0 38 100 25
1 39 2 46 190
9 78 10 80 230
20 42 21 89 170
27 26 28 68 170
35 41 36 99 270
43 36 44 63 280
51 15 52 27 150
57 14 58 29 190
64 2 65 90 160
75 33 76 35 290
78 5 79 100 290
88 28 89 40 190
94 7 95 50 250

11770

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^5$
• $100 \leq w \leq 10^{8}$
• $0 \leq x, y \leq 10^{8}$（$x, y$ 是起点、终点或矩形的顶点坐标）
• $N, w, x, y$ 都是整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$23$	$N \leq 500$
$2$	$35$	$N \leq 5\,000$
$3$	$31$	$x_{2} - x_{1} = 1$
$4$	$61$	无附加限制