#include<cstdio>
#include<algorithm>
#include<string.h>
#include<functional>
#include<cmath>
#include<iostream>
using namespace std;
class node
{
public:
int u,v;
int dist;
}edge[55002];
int num[509];
int find(int x)
{
return x==num[x]?x:num[x]=find(num[x]);
}
bool cmp(node xx,node yy)
{
return xx.dist<yy.dist;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=508;i++)
{
num[i]=i;
}
int a,b,x,mn=1,nn,nx,mx;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&x);
edge[i].u=a;edge[i].v=b;edge[i].dist=x;
}
while(k--)
{
int tt;
int con[510]={0};
scanf("%d",&tt);
for(int i=0;i<tt;++i)
{
scanf("%d",&con[i]);
}
for(int i=1;i<tt;++i)
num[find(con[i])]=find(con[i-1]);//连接幸存的道路
}
int xn=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)//xn为幸存的道路数
{
if(i==j)
continue;
if(num[j]==i)
xn++;
}
sort(edge+1,edge+1+m,cmp);
int sum=0;
for(int i=1;xn<n&&i<=m;i++)
{
int cx=find(edge[i].u),cy=find(edge[i].v);
if(cx!=cy)
{
num[cx]=cy;
sum+=edge[i].dist;
xn++;
}
}
if(xn<n)//因为初始化为1所以如果能连通,xn==n
sum=-1;
printf("%d\n",sum);
}
return 0;
}
分享到:
相关推荐
动态规划:http://acm.zju.edu.cn/forum/viewtopic.php?t=69 搜索:http://acm.zju.edu.cn/forum/viewtopic.php?t=67 数论:http://acm.zju.edu.cn/forum/viewtopic.php?t=66 几何:...
ACM大量习题题库 现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。除了USACO是为IOI准备外,其余几乎全 部是大学的ACM竞赛题库。 USACO http://ace.delos.com/usacogate 美国著名在线题库,专门为...
浙江大学在线题库:http://acm.zju.edu.cn/problems.php 浙江工业大学在线题库:http://acm.zjut.edu.cn 衡阳市第八中学信息学奥赛论坛&zju译题站:http://61.187.179.132:82/ UVA在线题库:...
408复试刷题 这个项目是我在2021年考研时的刷题集锦,其中包括王道机试指南第二版以及杭电OJ,前期用的C语言,后续改用C++,感谢作者炉灰 ...例题2.5 叠筐 http://acm.hdu.edu.cn/showproblem.php?pid=2
Hdu 1020解题报告,http://acm.hdu.edu.cn/showproblem.php?pid=1020
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
VISIT http://acm.baylor.edu/acmicpc/ BACK BACK BACK FORWARD VISIT http://www.ibm.com/ BACK BACK FORWARD FORWARD FORWARD QUIT Sample Output http://acm.ashland.edu/ http://acm.baylor.edu/acmicpc/ ...
另外,资料顺序并不按照时间排列,只是想起来了就上传。请大家见谅。) 国际程序语言设计和分析方面的顶级会议,PLDI 2011年的论文集,关于PLDI的档次,可以参考下面这个链接:...
zju 1048 Financial Managementhttp://acm.zju.edu.cn/show_problem.php?pid=1048
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
TagRec won the best poster award @ Hypertext 2014 (HT'14) conference: http://ht.acm.org/ht2014/index.php?awards.poster TagRec is also a main part of the recommender systems in the Layers project ...
3、林杰博客说明:http://linjie.org/2015/08/06/amr%E6%A0%BC%E5%BC%8F%E8%BD%ACmp3%E6%A0%BC%E5%BC%8F-%E5%AE%8C%E7%BE%8E%E8%A7%A3%E5%86%B3Linux%E4%B8%8B%E8%BD%AC%E6%8D%A20K%E9%97%AE%E9%A2%98/
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025
http://blog.csdn.net/acmmmm
另外,资料顺序并不按照时间排列,只是想起来了就上传。请大家见谅。) 软件工程研究领域的顶级国际会议,International Conference on Software Engineering 2011年的论文合集,只收录了正式的Regular Research ...
Mauro Pezzè是软件工程研究领域顶级期刊ACM Transactions on software engineering的副主编,同时是多个国际会议,如International Symposium on Software Testing and Analysis的委员会成员。 他领导的实验室主页...
几个程序设计的训练网站给大家,供大家参考! http://poj.org/ 北大的,比较难 http://acm.hdu.edu.cn/ 杭电的,相对容易 http://cm2prod.baylor.edu/welcome.icpc ACM/ICPC官方网站
本资源仅包含网页分割数据,其他资源,包括代码,模型,数据,文章可进入网页自行下载(http://mmgroup.cs.cityu.edu.hk/projects/visualflow/),使用代码或者数据请引用文章。 ...