← 返回题目列表

Codeforces · 1433/G

G. 降低运输成本

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

You are a mayor of Berlyatov.有 $$$n$$$ 个区,它们之间有 $$$m$$$ 双向道路。第 $$$i$$$ 条道路连接 $$$x_i$$$ 区和 $$$y_i$$$ 区。沿着这条路行驶的费用为$$$w_i$$$。每对区域之间都有一些路径,因此城市是相连的。

Berlyatov 有 $$$k$$$ 送货路线。第 $$$i$$$ 条路线从 $$$a_i$$$ 区前往 $$$b_i$$$ 区。每条路线上有一名快递员,快递员始终会选择从 $$$a_i$$$ 区到 $$$b_i$$$ 区最便宜(总成本最小)的路径来运送产品。

路线可以从区到本区,部分快递路线可以重合(需单独统计)。

您最多可以使一条道路的成本为零(即您最多选择一条道路并用 $$$0$$$ 更改其成本)。

设 $$$d(x, y)$$$ 为 $$$x$$$ 区和 $$$y$$$ 区之间最便宜的旅行费用。

如果您最佳地选择某条道路并使用 $$$0$$$ 更改其成本,您的任务是找到可以实现的最低总快递路线成本。换句话说,在最佳地应用上述操作后,您必须找到 $$$\sum\limits_{i = 1}^{k} d(a_i, b_i)$$$ 的最小可能值。

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 1000$$$; $$$n - 1 \le m \le min(1000, \frac{n(n-1)}{2})$$$; $$$1 \le k \le 1000$$$) — 地区数量、道路数量和快递路线数量。

接下来的 $$$m$$$ 行描述道路。第 $$$i$$$ 路由三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$w_i$$$ 给出($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 1000$$$),其中 $$$x_i$$$ 和$$$y_i$$$ 是第 $$$i$$$ 条道路连接的地区,$$$w_i$$$ 是其成本。保证每对区域之间都有路径,因此城市是相连的。还保证每对区域之间最多有一条道路。

接下来的 $$$k$$$ 行描述快递路线。第 $$$i$$$ 条路线由两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) 给出 - 第 $$$i$$$ 条路线的地区。路线可以从区到本区,有些快递路线可以重合(需要单独统计)。

输出

打印一个整数 - 如果您可以修建一些(最多一条)道路,您可以实现的最低总快递路线成本(即最小值 $$$\sum\limits_{i=1}^{k} d(a_i, b_i)$$$,其中 $$$d(x, y)$$$ 是地区 $$$x$$$ 和 $$$y$$$ 之间最便宜的旅行成本)成本为零。

示例

输入 #1

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

输出 #1

22

输入 #2

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

输出 #2

13

注意

第一个例子对应的图片:

在那里,您可以选择道路 $$$(2, 4)$$$ 或道路 $$$(4, 6)$$$。 Both options lead to the total cost $$$22$$$.

第二个例子对应的图片:

在那里,你可以选择道路$$$(3, 4)$$$。 This leads to the total cost $$$13$$$.