介绍
博主介绍：CSDN领军人物top1的作者，全网粉丝30w+，文章累计被阅读3800w+，直接帮助200+，间接帮助800+同学进入od
添加博主免费获取本题解析以及代码
文章目录
- 介绍
- 题目描述
- 输入描述
- 输出描述
- 解析+代码
- 最纯净OD社群
- 最新C、D卷题库
- 真实考试报告
- 真实面试实况
题目描述
现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间假设光纤的成本各不相同，且有些节点之间已经存在光纤相连。
请你设计算法，计算出能联通这些基站的最小成本是多少。
注意：基站的联通具有传递性，比如基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通。
输入描述
第一行输入表示基站的个数N，其中：
0 < N ≤ 20
第二行输入表示具备光纤直连条件的基站对的数目M，其中：
0 < M < N * (N - 1) / 2
从第三行开始连续输入M行数据，格式为
X Y Z P
其中：
X，Y 表示基站的编号
0 < X ≤ N
0 < Y ≤ N
X ≠ Y
Z 表示在 X、Y之间架设光纤的成本
0 < Z < 100
P 表示是否已存在光纤连接，0 表示未连接，1表示已连接
输出描述
如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本
如果给定条件，无法建设成功互联互通的5G网络，则输出 -1
用例1
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出
4
说明
只需要在1，2以及1，3基站之间铺设光纤，其成本为3+1=4
用例2
输入
3
1
1 2 5 0
输出
-1
说明
3基站无法与其他基站连接，输出-1
用例3
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出
1
说明
2，3基站已有光纤相连，只要在1，3基站之间铺设光纤，其成本为1
解析+代码
点击下方小卡片查看联系方式或者点击“联系我”免费获取解析+代码
最纯净OD社群
最纯净版的OD社群，包含2024最新华为OD题库、真实考试报告、真实面试实况等内容，独家资源其他地方基本找不到。
进入后可以获得一对一答疑服务，群内除了博主以外还有多为老师帮忙答疑，保证可以在3小时之内回复所有问题。
最新C、D卷题库
题库每周更新，根据最近考试的小伙伴反馈以及从其他合作伙伴的渠道提前获取最新真题，保证题库的时效性。题库在精不在多，如果需要AB卷的题库也可以免费领取
真实考试报告
内部小伙伴反馈的真实考试报告，都是最新的，每周会同步更新，个人隐私部分会删掉，只留题目、代码、分数以及时间等内容。
真实面试实况
内部小伙伴反馈的真实面试实况，都是最新的包括一面、二面、加面等，每周会同步更新，个人隐私部分会删掉，只留题目、代码、分数以及时间等内容。
