← 返回题目列表

AtCoder · jsc2021_h

H. 运输

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

分数: 600 点

问题陈述

在AtCoder共和国,有 N 城市称为 City 1 穿越城市 N 和 N 称为 Canal 的运河 1 通过运河 N.
运河 i 连接城市 i 和城市 A_i 双向,您必须支付 C_i 日元即可通过,但缴纳一次通行费后,可以在任何方向使用任意次数。
保证您可以使用一些运河从任何城市到达任何城市。

您被要求交付 M 该国的货物。的 i第一批货物应从城市交付 X_i 前往城市 Y_i.
除了使用运河之外没有其他办法来运送货物,但你自己可以在城市之间自由穿梭,而不需要使用运河。

找出运送所有物品所需支付的最低总通行费 M 货物。

约束

  • 3 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le A_i \le N
  • A_i \neq i
  • 1 \le C_i \le 10^9
  • 通过一些运河可以从任何城市到达任何城市。
  • 1 \le X_i \le N
  • 1 \le Y_i \le N
  • X_i \neq Y_i
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 C_1
A_2 C_2
A_3 C_3
\hspace{13pt} \vdots
A_N C_N
X_1 Y_1
X_2 Y_2
X_3 Y_3
\hspace{13pt} \vdots
X_M Y_M

输出

以整数形式打印您必须支付的最低通行费总额。


示例输入 1

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

示例输出 1

10

下图显示了该国的城市和运河,其中代表运河的线条上的数字代表通行费:
Figure

您可以按照以下方式运送货物,以赚取总费用 10 日元:

  • 的 1-st 货物:使用运河 1, 4 交付路线: 城市 4, 1, 3.
  • 的 2-nd 货物:使用运河 3, 1 在此路线上交付:城市 2, 3, 1.

示例输入 2

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

示例输出 2

13

多条运河可以连接同一对城市。


示例输入 3

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

示例输出 3

26