← 返回题目列表

Codeforces · 1580/E

E. 铁路建设

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

由于幻想乡的铁路系统经常拥堵,作为一名热情的工程师,Kawasiro Nitori 计划修建更多铁路来缓解拥堵。

幻想乡有$$$n$$$站,编号从$$$1$$$到$$$n$$$和$$$m$$$双向铁路。每条双向铁路连接两个不同的车站,并且具有正整数长度$$$d$$$。没有两条双向铁路连接相同的两个车站。此外,可以使用这些铁路从任何车站前往任何其他车站。在这$$$n$$$站中,$$$1$$$站是主站。您只需乘坐双向铁路即可从任何其他车站到达任何车站。

由于技术限制,Nitori 只能建造单向铁路,其长度可以是任意正整数。从车站 $$$u$$$ 建造一条单向铁路将花费 $$$w_u$$$ 单位资源,无论铁路终点在哪里。为了缓解拥堵,Nitori计划建成后从$$$1$$$站到任何其他车站至少有两条最短路径,并且这两条最短路径除了$$$1$$$站和航站楼外不经过同一站。此外,Nitori 也不想改变从 $$$1$$$ 站到任何其他站的最短路径的距离。

由于各种原因,有时修建新铁路的成本会不受控制地增加。此类事件总共会发生 $$$q$$$ 次,第 $$$i$$$ 次事件将为从 $$$k_i$$$ 站修建一条新铁路的成本增加 $$$x_i$$$ 的额外金额。

为了节省资源,在所有事件之前和每次事件之后,Nitori 希望你帮助她计算铁路建设的最低成本。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$、$$$1 \le m \le 3 \cdot 10^5$$$、$$$0 \le q \le 2\cdot10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^9$$$)。

接下来的 $$$m$$$ 行包含三个整数 $$$u$$$, $$$v$$$, $$$d$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$, $$$1 \le d \le 10^9$$$),表示连接车站 $$$u$$$ 和车站的双向铁路$$$v$$$,长度为$$$d$$$。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$k_i,x_i$$$ ($$$1 \le k_i \le n, 1 \le x_i \le 4 \times 10^8$$$)。

输出

打印$$$q+1$$$行,其中第$$$i$$$行包含一个整数,表示第$$$i-1$$$事件发生后铁路建设的最小成本(特别是第$$$0$$$事件表示没有发生事件)。

示例

输入 #1

5 5 1
1 1 1 1 1
1 2 1
2 3 1
2 4 1
3 5 1
4 5 1
1 2

输出 #1

3
9

输入 #2

8 11 0
14 4 16 15 1 3 1 14
4 2 1
1 2 3
7 5 4
2 3 1
8 6 2
8 5 5
5 4 5
7 6 7
3 5 5
1 6 6
8 1 4

输出 #2

46

输入 #3

10 16 8
29 1 75 73 51 69 24 17 1 97
1 2 18
2 3 254
2 4 546
2 5 789
5 6 998
6 7 233
7 8 433
1 9 248
5 10 488
2 6 1787
10 8 1176
3 8 2199
4 8 1907
2 10 1277
4 10 731
9 10 1047
1 11
1 9
8 8
1 3
2 19
9 5
9 4
7 6

输出 #3

34
45
54
54
57
76
96
112
112

注意

在第二个例子中,Nitori 可以建造如下铁路:$$$1 \rightarrow 2$$$、$$$1 \rightarrow 3$$$、$$$1 \rightarrow 4$$$、$$$2 \rightarrow 8$$$,成本为 $$$14 + 14 + 14 + 4 = 46$$$。