← 返回题目列表

Codeforces · 1869/B

B. 2D 旅行

中文机器翻译题面 查看原题

Piggy 生活在一个无限平面上,其上有笛卡尔坐标系。

飞机上有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$,前$$$k$$$个城市定义为主要城市。第 $$$i$$$ 个城市的坐标为 $$$(x_i,y_i)$$$。

小猪作为一名经验丰富的旅行者,希望在中考结束后来一次轻松的旅行。目前,他在城市 $$$a$$$,他想乘飞机前往城市 $$$b$$$。您可以在任意两个城市之间飞行,并且在旅行时可以按任意顺序访问多个城市,但最终目的地必须是城市$$$b$$$。

由于主要城市之间的贸易活跃,可以免费乘坐飞机在它们之间旅行。正式而言,两个城市 $$$i$$$ 和 $$$j$$$ 之间的机票价格 $$$f(i,j)$$$ 定义如下:

$$$$$$ f(i,j)= \begin{cases} 0, & \text{如果城市 }i \text{ 和 }j \text{ 都是主要城市} \\ |x_i-x_j|+|y_i-y_j|, & \text{否则} \end{cases} $$$$$$

小猪不想节省时间,但他想省钱。所以你需要告诉他,如果他可以乘坐任意数量的航班,那么所有机票总费用的最小值是多少。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含四个整数 $$$n$$$、$$$k$$$、$$$a$$$ 和 $$$b$$$ ($$$2\le n\le 2\cdot 10^5$$$、$$$0\le k\le n$$$、$$$1\le a,b\le n$$$、$$$a\ne b$$$) — 城市数量、主要城市数量以及起始和结束城市数量。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$) — 第 $$$i$$$ 城市的坐标。前 $$$k$$$ 行描述了主要城市。保证所有坐标都是成对不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 所有机票总价的最小值。

示例

输入 #1

5
6 2 3 5
0 0
1 -2
-2 1
-1 3
2 -2
-3 -3
2 0 1 2
-1000000000 -1000000000
1000000000 1000000000
7 5 4 2
154 147
-154 -147
123 456
20 23
43 20
998 244
353 100
3 1 3 1
0 10
1 20
2 30
4 3 2 4
0 0
-100 100
-1 -1
-1 0

输出 #1

4
4000000000
0
22
1

注意

在第一个测试用例中:

主要城市被标记为红色。

选择航班的最佳方式是:$$$3\rightarrow 1 \rightarrow 2 \rightarrow 5$$$,费用为$$$3+0+1=4$$$。请注意,$$$1\rightarrow 2$$$ 航班的费用为 $$$0$$$,因为 $$$1$$$ 和 $$$2$$$ 都是主要城市。

在第二个测试用例中,由于只有 $$$2$$$ 个城市,因此唯一的方法是从 $$$1$$$ 城市飞往 $$$2$$$。

在第三个测试用例中,由于城市$$$2$$$和$$$4$$$都是主要城市,Piggy可以直接从城市$$$2$$$乘坐航班飞往$$$4$$$,费用为$$$0$$$。

在第四个测试用例中,小猪可以选择乘坐以下航班:$$$3\rightarrow 2\rightarrow 1$$$,费用为$$$11+11=22$$$。