← 返回题目列表

Codeforces · 1343/E

E. 权重分布

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

给你一个无向无权图,由 $$$n$$$ 顶点和 $$$m$$$ 边(代表 Bertown 的地图)和长度为 $$$m$$$ 的价格数组 $$$p$$$ 组成。保证每对顶点(区域)之间都有一条路径。

Mike 计划了一次从顶点(区)$$$a$$$ 到顶点(区)$$$b$$$,然后从顶点(区)$$$b$$$ 到顶点(区)$$$c$$$ 的行程。他可以访问同一地区两次或更多次。但有一个问题:城市当局想对这条路的使用设定一个价格,所以如果有人沿着这条路走,那么他就应该支付与这条路相对应的价格(他每次沿着这条路走都要付钱)。将使用 $$$p$$$ 的价格列表已准备就绪,他们只想将其分配到镇上的所有道路之间,以便数组中的每个价格恰好对应于一条道路。

您是 Mike 的好朋友(突然成为 Bertown 的市长),并且想帮助他尽可能便宜地旅行。因此,您的任务是在道路之间分配价格,如果迈克选择最佳路径,则行程的价格可能是最低的。请注意,您无法在行程开始后重新安排价格。

您必须回答 $$$t$$$ 独立测试用例。

输入

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

测试用例的第一行包含五个整数 $$$n, m, a, b$$$ 和 $$$c$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n-1 \le m \le min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$$$, $$$1 \le a, b, c \le n$$$) — Mike 行程中的顶点数、边数和区域数。

测试用例的第二行包含 $$$m$$$ 整数 $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le 10^9$$$),其中 $$$p_i$$$ 是数组中的第 $$$i$$$ 价格。

测试用例中的以下 $$$m$$$ 行表示边:边 $$$i$$$ 由一对整数 $$$v_i$$$、$$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$) 表示,它们是边连接的顶点的索引。给定图中没有循环或多重边,i。 e.对于每对 ($$$v_i, u_i$$$),边数组中没有其他对 ($$$v_i, u_i$$$) 或 ($$$u_i, v_i$$$),并且对于每对 $$$(v_i, u_i)$$$ 满足条件 $$$v_i \ne u_i$$$。保证给定的图是连通的。

保证$$$n$$$之和(以及$$$m$$$之和)不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$, $$$\sum m \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案 - 如果您在边之间最佳分配价格,则迈克行程的最低可能价格。

示例

输入 #1

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

输出 #1

7
12

注意

示例的第一个测试用例的可能解决方案之一:

示例的第二个测试用例的可能解决方案之一: