← 返回题目列表

Codeforces · 1737/D

D. 埃拉和接线向导

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

Ela 需要通过机器网络将一个大包裹从机器 $$$1$$$ 发送到机器 $$$n$$$。目前,就网络情况而言,她抱怨网络太慢,包裹无法及时到达。幸运的是,一位接线向导向她伸出了援助之手。

网络可以表示为具有 $$$n$$$ 个节点的无向​​连通图,每个节点代表一台机器。 $$$m$$$ 电线用于连接它们。电线$$$i$$$用于连接机器$$$u_i$$$和$$$v_i$$$,重量为$$$w_i$$$。上述大包裹,如果通过线路 $$$i$$$,将从机器 $$$u_i$$$ 移动到机器 $$$v_i$$$(反之亦然),精确时间为 $$$w_i$$$ 微秒。接线向导可以任意次数地使用他的法术。对于每个咒语,他将选择索引$$$i$$$的电线,连接机器$$$u_i$$$和$$$v_i$$$,并按照以下步骤重新接线:

- 选择通过此电线连接的一台机器。不失一般性,我们选择$$$v_i$$$。
- 选择当前连接到$$$v_i$$$(包括$$$u_i$$$)的机器,将其命名为$$$t_i$$$。从 $$$v_i$$$ 断开索引为 $$$i$$$ 的电线,然后用它连接 $$$u_i$$$ 和 $$$t_i$$$。

电线$$$i$$$的重新布线将花费$$$w_i$$$微秒,并且此操作后电线的重量不会改变。重新接线后,机器可能会有一些电线与其自身连接。此外,接线向导警告 Ela 重新接线可能会导致某些机器之间暂时断开连接,但 Ela 无论如何都忽略了它。她的任务是尽快将大包裹从机器 $$$1$$$ 发送到机器 $$$n$$$。请注意,巫师可以在一根线上使用他的咒语零次、一次或多次。为了确保网络在传输大包裹时无缝工作,一旦包裹开始从机器 $$$1$$$ 传输,接线向导就无法再使用他的咒语来移动电线。

Ela 想知道,在接线向导的帮助下,将大包裹从机器 $$$1$$$ 传输到 $$$n$$$ 所需的最少时间是多少。

输入

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

第一行包含 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 500$$$, $$$n - 1 \le m \le 250 000$$$),分别是节点数和电线数。

对于接下来的 $$$m$$$ 行,第 $$$i$$$ 行将包含 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^9$$$) - 通过$$$i$$$-th 条边及其权重。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$250 000$$$。每个测试用例中的图都保证是连通的,没有自环,但可以包含多条边。

输出

对于每个测试用例,输出一个整数表示将大包从机器 $$$1$$$ 传输到 $$$n$$$ 所需的最短时间。

示例

输入 #1

3
8 9
1 2 3
6 4 5
3 5 6
6 1 3
7 4 4
3 8 4
2 3 3
7 8 5
4 5 2
4 5
1 2 1
2 4 1
3 4 1
3 1 1
1 3 2
8 8
4 6 92
7 1 65
6 5 43
6 7 96
4 3 74
4 8 54
7 4 99
2 5 22

输出 #1

9
2
154

注意

这是示例输入中第一个测试用例的图表:

Ela 可以要求接线向导在索引为 $$$7$$$ 的线路上使用他的咒语,该咒语连接机器 $$$2$$$ 和 $$$3$$$。然后,由于机器 $$$8$$$ 连接到机器 $$$3$$$,接线向导可以在 $$$3$$$ 微秒内从机器 $$$7$$$ 断开电线 $$$7$$$ 并将其连接到机器 $$$8$$$(电线重量 $$$3$$$)。

之后,包可以在$$$6$$$微秒内从机器$$$1$$$发送到机器$$$8$$$。因此,答案是 $$$3 + 6 = 9$$$ 微秒。

这是示例输入中第三个测试用例的图表: