CF1163F Indecisive Taxi Fee

题目描述

在 Kuro 和 Shiro 居住的 Capypaland 城市中，有 $n$ 个城镇，编号从 $1$ 到 $n$，并有 $m$ 条双向道路，编号从 $1$ 到 $m$，连接着这些城镇。第 $i$ 条道路连接城镇 $u_i$ 和 $v_i$。由于城镇之间出行较为困难，出租车行业在这里非常流行。为了在激烈的竞争中生存下去，每家出租车公司都需要为顾客提供独特的服务。

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 想知道，在每个方案下，她从城镇 $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$ 条道路连接的两个端点及其原始价格。

保证至少存在一条从城镇 $1$ 到城镇 $n$ 的路径。

接下来的 $q$ 行中，每行包含两个整数 $t_j$ 和 $x_j$（$1 \leq t_j \leq m, 1 \leq x_j \leq 10^9$）——表示 Kuro 计划更改的道路编号及其新价格。

输出格式

输出 $q$ 个整数，第 $i$ 个整数表示在第 $i$ 个方案下，Shiro 从城镇 $1$ 到城镇 $n$ 所需支付的最低费用。

输入输出样例 #1

输入 #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

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

输入 #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$。

由 ChatGPT 4.1 翻译