4500: 【最小生成树】2024D-5G 网络建设

金币值:1 时间限制:2.000 s 内存限制:128 M
正确:119 提交:286 正确率:41.61% 命题人:

题目描述

现需要在某城市进行 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

输入样例    复制

3
3
1 2 3 0
1 3 1 0
2 3 5 0

输出样例    复制

4

提示

只需要在 1,2 以及 2,3 基站之间铺设光纤,其成本为 3+1=4