#P1428. 2023.08.25-YYsp笔试-第三题-区域联通
2023.08.25-YYsp笔试-第三题-区域联通
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
有编号从1到n的n个区域,这些区域之间通过路径进行连接。每条路径都连接两个区域,并且可以双向通行。
每个路径都有一个权值,这个权值由路径上的数字表示。每个路径上的数字都是唯一的。
现在,由于某种原因,所有的路径都处于阻塞状态。作为一名勇敢的探索者,塔子哥的任务是找出一种方式,疏通最少的路径,使得所有的区域都至少通过一个可以通行的路径与其他区域连接。
给定一部分路径的信息 [X,Y,M],表示区域 X 和区域 Y 之间可以疏通一条路径,并且权值为 M。
塔子哥的目标是计算联通所有区域所需的路径的最小权值之和。如果无法联通所有区域,则输出-1。
第一行为两个整数 n,m,分别表示区域和路径的数量。
接下来 m 行每行三个整数 x,y,v,分别表示 x 区域和 y 区域之间有一条权值为 v 的路径。
$1 \le x,y \le n \le 5000, 1 \le m \le 10^5, 1 \le v \le 1000$。
计算联通所有区域的最小权值,如果无法联通,则输出 −1。
5 6
1 4 10
1 1 13
3 5 14
2 3 10
4 3 15
3 1 5
39
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.