E - QS Network

题目链接：

题目：

在星系cgb的w-503行星中，有一种名为QS的智能生物。 QS通过网络相互通信。如果两个QS想要连接，他们需要购买两个网络适配器（每个QS一个）和一段网络电缆。请注意，一个网络适配器只能在单个连接中使用。（即，如果QS想要设置四个连接，则需要购买四个适配器）。在通信过程中，QS将其消息广播到它所连接的所有QS，接收消息的QS组将消息广播到它们所连接的所有QS，重复该过程直到所有QS都收到消息。

    示例如下所示：

    QS网络示例，QS A想要发送消息。

    步骤1. QS A向QS B和QS C发送消息;

    步骤2. QS B向QS A发送消息; QS C向QS A和QS D发送消息;

    步骤3.该过程终止，因为所有QS都收到了该消息。

    每个QS都有其优质的网络适配器品牌，并始终在其所有连接中购买该品牌。 QS之间的距离也不同。考虑到每个QS优先品牌的网络适配器的价格以及每对QS之间的电缆价格，您的任务是编写一个程序来确定设置QS网络的最低​​成本。

输入

    输入的第一行包含一个整数t，表示数据集的数量。

    从第二行开始，有t个数据集。

    在单个数据集中，第1行包含一个表示QS数的整数n。

    第二行包含n个整数，表示每个QS最喜欢的网络适配器的价格。

    在第3行到第n + 2行包含一个矩阵，表示ecah对QS之间的电缆价格。

    限制：

    输入中的所有整数都是非负数且不超过1000。

产量

    对于每个数据集，输出一行中的最小成本。不需要额外的空行。

样本输入

    1

    3

    10 20 30

    0 100 200

    100 0 300

    200 300 0

样本输出

    370

思路：这道题要处理的东西比模板多一点，就是每个QS都有自己喜欢的适配器价格，然而两人之间需要有电缆，电缆也因人而异，

所以以往的node[i].w+=x改成node[i].w+=x+a[i]+a[j]，就是两者之间的适配器加上i->j和j->i之间的电缆价格就行了，主意数组要开大

我用的2e5+10wa掉了，用的2e6+10就ac了

 

//// Created by hy on 2019/7/30.//#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const int maxn=2e6+10;int father[maxn],a[maxn];struct Node{ int u,v,w; bool operator<(const Node &other)const{ return this->w