B - Networking
题目链接:
题目:
您被分配设计广泛区域中某些点之间的网络连接。您将获得该区域中的一组点,以及可连接成对点的电缆的一组可能路线。对于两点之间的每条可能路线,您将获得连接该路线上的点所需的电缆长度。请注意,两个给定点之间可能存在许多可能的路径。假设给定的可能路线(直接或间接)连接该区域中的每两个点。 您的任务是为该区域设计网络,以便在每两个点之间存在连接(直接或间接)(即,所有点都是互连的,但不一定是通过直接电缆),并且总长度为用过的电缆很小。输入 输入文件由许多数据集组成。每个数据集定义一个必需的网络。集合的第一行包含两个整数:第一行定义给定点的数量P,第二行定义点之间给定路径的数量R.以下R行定义了点之间的给定路线,每条线给出三个整数:前两个数字标识点,第三个给出路线的长度。数字用空格分隔。仅给出一个数字P = 0的数据集表示输入的结束。数据集用空行分隔。 最大点数为50.给定路线的最大长度为100.可能的路线数量不受限制。节点用1和P(含)之间的整数标识。两个点i和j之间的路线可以给出为i j或j i。产量 对于每个数据集,在单独的行上打印一个数字,该行显示用于整个设计网络的电缆的总长度。样本输入 1 0 2 3 1 2 37 2 1 17 1 2 68 3 7 1 2 19 2 3 11 3 1 7 1 3 5 2 3 89 3 1 91 1 2 32 5 7 1 2 5 2 3 7 2 4 8 4 5 11 3 5 10 1 5 6 4 2 12 0样本输出 0 17 16 26
思路:求最小生成树
//// Created by hy on 2019/7/30.//#include#include #include #include #include #include using namespace std;typedef long long ll;const int maxn=2e5+10;struct Node{ int from,to,value; bool operator<(const Node &other)const{ return this->value