← 返回题目列表

Codeforces · 2239/E

E. 这个世界的终结,

中文机器翻译题面 查看原题
...还有穿越月球海洋的女孩。
— 弗鲁姆斯

给定一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的无向图。第 $$$i$$$ 个顶点具有关联值 $$$\mathrm{val}_i$$$。第 $$$j$$$ 条边连接顶点 $$$u_j$$$ 和 $$$v_j$$$,并具有两个属性:容量 $$$w_j$$$ 和下限 $$$\mathrm{low}_j$$$。保证所有边的 $$$w_j \ge \mathrm{low}_j$$$ 。

您想要从顶点 $$$s$$$ 开始行走。在步行开始之前,您必须选择任意非负整数 $$$h_{start}$$$ 作为初始状态参数。

如果当前位于状态为 $$$h$$$ 的顶点 $$$u$$$,则可以遍历连接 $$$u$$$ 和 $$$v$$$ 的边 $$$j$$$ 当且仅当 $$$w_j \ge h$$$。遍历这条边并到达顶点 $$$v$$$ 后,状态参数 $$$h$$$ 更新为 $$$\max(h, \mathrm{low}_j)$$$。

让行走在某个顶点 $$$t$$$ 处结束。你必须穿越 至少一条边 这种步行的。的 分数 本实验的 定义为 $$$\mathrm{val}_t + h_{start}$$$。请注意,我们感兴趣的是 最终顶点值 和 初始状态参数,不是最终状态参数。

对于从 $$$1$$$ 到 $$$n$$$ 的每个起始顶点 $$$s$$$,计算可达到的最大可能分数。如果不可能从$$$s$$$开始遍历任何边,则输出$$$-1$$$。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 5\cdot 10^5, 0 \le m \le 5\cdot 10^5$$$) — 顶点数和边数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$\mathrm{val}_1, \mathrm{val}_2, \ldots, \mathrm{val}_n$$$ ($$$1 \le \mathrm{val}_i \le 10^9$$$) — 顶点的值。

接下来的 $$$m$$$ 行描述了边缘。第 $$$j$$$ 行包含四个整数 $$$u_j, v_j, w_j, \mathrm{low}_j$$$ ($$$1 \le u_j, v_j \le n, u_j \neq v_j$$$; $$$1 \le \mathrm{low}_j \le w_j \le 10^9$$$) — 的端点和属性第 $$$j$$$ 条边。

该图不保证是连通的,并且可能包含多条边。

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

输出

对于每个测试用例,输出 $$$n$$$ 个由空格分隔的整数。第 $$$i$$$ 个整数应该是从顶点 $$$i$$$ 开始可达到的最大分数,如果没有边可以遍历,则为 $$$-1$$$。

示例

输入
复制

9
3 2
10 20 5
1 2 5 2
2 3 4 3
2 1
100 10
1 2 10 5
2 0
50 50
1 0
114514
4 1
1 2 3 4
3 4 2 1
3 2
1 4 1
1 3 4 1
1 2 2 1
3 2
10 3 2
2 3 4 4
2 1 3 2
3 2
5 2 2
3 2 4 4
1 3 5 5
5 9
857147200 381798978 633421584 956726892 315899900
2 1 883474754 795831571
2 4 657281748 375466725
1 3 666641114 444218918
2 3 901861650 790895313
3 2 613790652 96876004
2 5 852725279 216601090
3 4 500240642 193633892
2 5 210434355 130646156
3 2 457018372 279005896

输出
复制

25 25 24
110 110
-1 -1
-1
-1 -1 6 6
6 6 6
13 13 7
10 9 10
1740621954 1740621954 1740621954 1614008640 1709872479

注意

在第一个测试用例中,以下是每个起始节点的最佳 $$$h_{start}$$$ 值和路径:

  • 对于节点$$$1$$$,最佳使用$$$h_{start}=5$$$。然后,获取从节点 $$$1$$$ 到节点 $$$2$$$ 的路径。 $$$h$$$ 更新为 $$$\operatorname{max}(5,2)=5$$$。路径结束,得分为$$$20+5=25$$$。
  • 对于节点$$$2$$$,最佳使用$$$h_{start}=5$$$。然后,采用从节点 $$$2$$$ 到节点 $$$1$$$ 的路径,然后从节点 $$$1$$$ 到节点 $$$2$$$ 的路径。分数是$$$20+5=25$$$。
  • 对于节点$$$3$$$,最佳使用$$$h_{start}=4$$$。然后,获取从节点 $$$3$$$ 到节点 $$$2$$$ 的路径。分数是$$$20+4=24$$$。

在第三个测试用例中,由于没有边与任一节点相关,因此两个节点的答案都是 $$$-1$$$。