← 返回题目列表

Codeforces · 1915/G

G. 自行车

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

Slavic 的所有朋友都计划从他们居住的地方骑自行车去参加聚会。除了斯拉夫之外,他们都有自行车。他们可以穿越 $$$n$$$ 的城市。他们都住在城市 $$$1$$$ 并想去参加位于城市 $$$n$$$ 的聚会。城市地图可以看作是具有 $$$n$$$ 节点和 $$$m$$$ 边的无向图。边 $$$i$$$ 连接城市 $$$u_i$$$ 和 $$$v_i$$$,长度为 $$$w_i$$$。

斯拉夫没有自行车,但他有的是钱。每个城市都有一辆自行车待售。第 $$$i$$$ 个城市的自行车的缓慢系数为 $$$s_{i}$$$。一旦 Slavic 购买了一辆自行车,他就可以随时使用它从当前所在的城市前往任何邻近的城市,只需花费 $$$w_i \cdot s_j$$$ 时间,考虑到他正在使用他拥有的自行车 $$$j$$$ 穿越边缘 $$$i$$$。

Slavic 可以购买任意数量的自行车,因为钱对他来说不是问题。由于 Slavic 讨厌骑自行车旅行,因此他希望在尽可能短的时间内从住处到达聚会场所。而且,由于他的信息学技能相当生疏,他向你寻求帮助。

斯拉夫从城市 $$$1$$$ 到城市 $$$n$$$ 最短需要多少时间?斯拉夫人没有自行车就不能旅行。保证斯拉夫可以从 $$$1$$$ 城市前往任何其他城市。

输入

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

每个测试用例的第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 1000$$$; $$$n - 1 \leq m \leq 1000$$$) - 分别是城市数量和道路数量。

以下 $$$m$$$ 行中的第 $$$i$$$ 行每行包含三个整数 $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$; $$$1 \leq w_i \leq 10^5$$$),表示城市 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条长度为 $$$w_i$$$ 的道路。同一对城市可以通过多条道路连接。

下一行包含 $$$n$$$ 整数 $$$s_1, \ldots, s_n$$$ ($$$1 \leq s_i \leq 1000$$$) — 每辆自行车的缓慢系数。

所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$1000$$$。

对输入的附加约束:可以从城市 $$$1$$$ 前往任何其他城市。

输出

对于每个测试用例,输出一个整数,表示斯拉夫语从城市 $$$1$$$ 开始到达城市 $$$n$$$ 的最短时间。

示例

输入 #1

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

输出 #1

19
36
14