5G网络建设 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，

接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间架设光纤的成本各不相同，且有些节点之间已经存在光纤相连，

请你设计算法，计算出能联通这些基站的最小成本是多少。

注意，基站的联通具有传递性，入基站A与基站B架设了光纤基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通

输入描述

第一行输入表示基站的个数N，其中0

第二行输入表示具备光纤直连条件的基站对的数目M,其中0 < M < N * (N - 1) / 2

从第三行开始连域输入M行数据，将式为：X Y Z P，

• 其中X Y表示基能的编号，0
• Z表示在X Y之间架设光纤的成本，其中0 < Z < 100，
• P表示是否已存在光纤连接，0表示未连接1表示已连接.

输出描述