[R4F]交通问题 - 代码源竞赛平台

时空限制

2S/512M

题目描述

交通示意图由 $n$ 纵 $n$ 横共 $2\times n$ 条马路构成，如下图所示是一个 $n=7$ 的交通示意图。

任意两条纵横马路的交点是一个路口，所以每条马路上都有 $n$ 个路口，共有 $n^2$ 个路口，定义第 $i$ 条纵向马路与第 $j$ 条横向马路的交点为路口 $(i,j)$。

其中只有 $m$ 个路口允许转向，第 $i$ 个允许转向的路口为 $(x_i,y_i)$，剩下的路口在经过时只能保持原有的方向不变。

车辆从一个路口沿着马路开往相邻的另一个路口需要 $1$ 分钟，在路口改变方向需要 $k$ 分钟，现在你从路口 $(SX,SY)$ 出发，求到达路口 $(TX,TY)$ 最少需要花多少时间。出发和到达时的方向不限。

格式

输入格式

第一行包含三个整数 $n,m,k$，分别表示每个方向的马路数量，能转向的路口数量，和每次在路口改变方向所需的时间。

第二行包含 $4$ 个整数 $SX,SY,TX,TY$，分别表示起点路口和终点路口的位置。

接下来 $m$ 行，每行两个整数 $x_i$ 和 $y_i$，分别表示能转向的路口的位置。

输出格式

输出一个整数表示从起点路口到终点路口所需的最短时间。无解输出 $-1$。

样例

样例输入 #1

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

样例输出 #1

13

样例解释 #1

时间最短的路线如下图：

样例输入 #2

7 9 2
1 4 6 6
1 1
3 4
4 2
4 5
5 2
5 4
6 5
7 1
7 6

样例输出 #2

21

样例解释 #2

时间最短的路线如下图：

数据规模

对于 $100\%$ 的数据，$2\leq n\leq 10^9$，$0\leq m \leq 2\times 10^5$，$0\leq k \leq 10^{12}$，$1\leq SX,SY,TX,TY,x_i,y_i\leq n$。

数据保证任意两个能转向的路口的位置不同，但不保证起点路口或终点路口的位置与能转向的路口的位置不同。

测试点编号	$n$	$m$	特殊性质
1	$\leq 1000$	$\leq 1000$	$k=0$
2~3			$\text{无}$
4		$\leq 2\times 10^5$
5~6	$\leq 10^9$		$k=0$
7~10			$\text{无}$