← 返回题目列表

Codeforces · 1163/F

F. 犹豫不决的出租车费

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

在Kuro和Shiro居住的Capypaland市,有$$$n$$$个城镇,编号从$$$1$$$到$$$n$$$,有$$$m$$$双向道路连接它们,编号从$$$1$$$到$$$m$$$。第 $$$i$$$ 条道路连接城镇 $$$u_i$$$ 和 $$$v_i$$$。由于城镇之间的交通相当困难,因此出租车行业在这里非常受欢迎。为了在激烈的竞争中生存,每个出租车公司都必须为他们的客户找到独特的特征。

Kuro 是一家出租车公司的老板。他决定为他的出租车品牌引入一种新的收费模式,每次乘车的费用不是根据行程长度计算,而是根据所行驶道路的价格总和计算。每条 $$$m$$$ 道路的价格均由 Kuro 亲自决定。

截至目前,道路 $$$i$$$ 的价格为 $$$w_i$$$,因此出租车经过道路 $$$e_1、e_2、\ldots、e_k$$$ 的费用为 $$$\sum_{i=1}^k w_{e_i}$$$。

然而,Kuro本人是一个优柔寡断的人,所以他起草了$$$q$$$计划来改变道路价格。各方案均以原价格$$$w_i$$$为基础,但单条道路$$$t_j$$$的价格改为$$$x_j$$$。请注意,这些计划是相互独立的。

Shiro 是 Kuro 出租车品牌的常客,因为她每天使用出租车从镇 $$$1$$$ 到镇 $$$n$$$。由于她是一位常客,Kuro 决定在向公众发布之前向她展示他所有的 $$$q$$$ 计划。现在,Shiro 想知道对于每个 Kuro 的计划,从 $$$1$$$ 镇到 $$$n$$$ 镇所需支付的最低费用。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m, q \le 2 \cdot 10^5$$$)——分别是 Kuro 起草的城镇数量、道路数量和计划数量。

下一个 $$$m$$$ 的第 $$$i$$$ 包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$u_i \ne v_i$$$) — 两个端点以及第 $$$i$$$ 条道路的原始价格。

保证至少有一种方式可以使用这些 $$$m$$$ 双向道路从城镇 $$$1$$$ 前往城镇 $$$n$$$。

接下来的 $$$q$$$ 行包含两个整数 $$$t_j$$$ 和 $$$x_j$$$ ($$$1 \leq t_j \leq m, 1 \leq x_j \leq 10^9$$$) - Kuro 计划更改的道路索引及其新价格。

输出

打印 $$$q$$$ 整数 - Shiro 在每个 $$$q$$$ 计划中从城镇 $$$1$$$ 到城镇 $$$n$$$ 必须支付的最低费用。

示例

输入 #1

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

输出 #1

4
2
5
6
3
1

输入 #2

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

输出 #2

1
2
2
3

输入 #3

2 1 1
1 2 1
1 3

输出 #3

3

注意

在第一个示例中,Capypaland 的原始概述如下所示,其中每条道路旁边的数字表示道路的原始价格,

第一个计划的概述,

Shiro在此计划中必须支付的最低费用是$$$4$$$,对应路径$$$1 \rightarrow 4$$$。

第二个计划的概述,

Shiro在此计划中必须支付的最低费用是$$$2$$$,对应路径$$$1 \rightarrow 3 \rightarrow 4$$$。

第三个计划概述,

Shiro在此计划中必须支付的最低费用是$$$5$$$,对应路径$$$1 \rightarrow 2 \rightarrow 4$$$。