• Source 
    1. #include<bits/stdc++.h>
    2. using namespace std;
    3.  
    4. struct canh
    5. {
    6. 	int dau,cuoi;
    7. 	int trongso;
    8. };
    9. long long ntest,m,i,u,c,v;
    10. long long d[101],dem=0,dad[101];
    11. canh CA[10001];
    12. long long chiphi=0;
    13.  
    14. int FindDad(int u)
    15. {
    16. 	if(dad[u]==-1)
    17. 		{
    18. 			dad[u]=u;return u;
    19. 		}
    20. 	else return dad[u];
    21. }
    22.  
    23. void Add(int u,int v)
    24. {
    25. 	if(u>v)	
    26. 		for(int i=1;i<=m;i++)
    27. 			{
    28. 				if(dad[i]==u)
    29. 					dad[i]=v;
    30. 			}
    31. 	else if(v>u) 
    32. 		for(int i=1;i<=m;i++)
    33. 				{
    34. 					if(dad[i]==v)
    35. 						dad[i]=u;
    36. 				}		
    37. }
    38. void QUICK_SORT(canh CA[],int left,int right)
    39. {
    40. 	if(left==right)
    41. 		return;
    42. 	 if(left<right)
    43. 		{
    44. 			int k=(left+right)/2;
    45. 			int i=left,j=right;
    46. 		while(i<=j)
    47. 			{
    48. 				while(CA[i].trongso<CA[k].trongso) i++;
    49. 				while(CA[j].trongso>CA[k].trongso) j--;
    50. 				if(i<=j)
    51. 					{
    52. 						canh g=CA[i];
    53. 						CA[i]=CA[j];
    54. 						CA[j]=g;
    55. 						i++,j--;
    56. 					}
    57. 			}
    58. 		QUICK_SORT(CA,left,j);
    59. 		QUICK_SORT(CA,i,right);	
    60. 		}
    61. }
    62.  
    63.  
    64. void quickSort(canh CA[], int l, int r)
    65. {
    66. 	if(l<r){
    67.  
    68.     int key = CA[(l+r)/2].trongso;
    69.     int i = l, j = r;
    70.     while(i <= j)
    71.     {
    72.         while(CA[i].trongso < key) i++;       
    73.         while(CA[j].trongso > key) j--;       
    74.         if(i <= j)
    75.         {
    76.             if (i < j)
    77.             	{
    78.             		canh g=CA[i];
    79. 					CA[i]=CA[j];
    80. 					CA[j]=g;
    81. 				}
    82.             i++;
    83.             j--;
    84.         }
    85.     }
    86.     quickSort(CA, l, j);   
    87.     quickSort(CA, i, r); 
    88. 	}
    89. }
    90.  
    91. void Selec(canh CA[],int n)
    92. {
    93. 	for(int i=1;i<=n-1;i++)
    94. 		for(int j=i+1;j<=n;j++)
    95. 			if(CA[i].trongso>CA[j].trongso)
    96. 				{
    97. 					canh g=CA[i];
    98. 					CA[i]=CA[j];
    99. 					CA[j]=g;
    100. 				}
    101. }
    102. void process()
    103. {
    104. 	//QUICK_SORT(CA,1,dem);
    105. 	//Selec(CA,dem);
    106. 	quickSort(CA,1,dem);
    107. 	int demcanh=0,demdinh=0;
    108. 	int i1=dem,x,y;
    109. 	while(demcanh<m-1&&demdinh<m)
    110. 	{
    111. 		x=FindDad(CA[i1].dau);
    112. 		if(x==-1) demdinh++;
    113. 		y=FindDad(CA[i1].cuoi);
    114. 		if(y==-1) demdinh++;
    115. 		if(x!=y)
    116. 			{
    117. 				Add(x,y);demcanh++;
    118. 				chiphi-=CA[i1].trongso;
    119. 			}
    120. 		//cout <<CA[i1].dau<<" "<<CA[i1].cuoi<<" "<<CA[i1].trongso<<endl;
    121. 		i1--;
    122. 	}
    123. }
    124. int main()
    125. {
    126. 	//freopen("input.txt.txt","r",stdin);
    127. 	ios::sync_with_stdio(false);
    128. 	cin>>ntest;
    129. 	for(int j=1;j<=ntest;j++)
    130. 		{
    131. 			cin >>m;chiphi=0,dem=0;
    132. 			for(int jj=1;jj<=m;jj++)
    133. 				{
    134. 					cin >>i>>u>>c; 
    135. 					d[i]=u,dad[i]=-1;
    136. 					for(int j1=1;j1<=c;j1++)
    137. 						{
    138. 							cin >>v;
    139. 							if(i>v)	
    140. 								{
    141. 									CA[++dem].dau=i; CA[dem].cuoi=v;
    142. 									CA[dem].trongso=d[i]+d[v];
    143. 									chiphi+=CA[dem].trongso;
    144. 								}
    145. 						}
    146. 				}
    147. 				process();
    148. 				//for(int i=1;i<=dem;i++)
    149. 				//	cout <<CA[i].dau<<"  "<<CA[i].cuoi<<"  "<<CA[i].trongso<<endl;
    150. 				cout <<chiphi<<endl;
    151.  
    152. 		}
    153. }