学步园

In 2100, since the sea level rise, most of the cities disappear. Though some survived cities are still connected with others, but most of them become disconnected. The government wants to build some roads to connect all of these cities
again, but they don’t want to take too much money.

The first line contains the number of test cases.
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected
cities.
To make it easy, the cities are signed from 1 to n.
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.

For each case, output the least money you need to take, if it’s impossible, just output -1.

1
6 4 3
1 4 2
2 6 1
2 3 5
3 4 33
2 1 2
2 1 3
3 4 5 6

1
一开始直接写出的prim算法G++超时，c++504MS，后来想出了把prim算法中的两个for可以变成一个for，G++968MS 险过，后自写一个scanf函数C++203MS。
不自写一个输入函数的话会要很多时间，因为在调用库存里的输入函数时，程序会把当前的信息全部都存起来，然后再去执行输入，输完之后再把所有的信息又取出来，
再执行下面的程序，所以在这个存取过程中肯定是要时间。而自己写的就直接用，不必这些过程。
#include<stdio.h>
#include<iostream>
using namespace std;
int node[505],s[505],map[505][505],sum,n,INF=100000000;
void set()
{
    for(int i=1;i<=n;i++)
    {
        node[i]=INF; s[i]=0;
        for(int j=i+1;j<=n;j++)
        map[j][i]=map[i][j]=INF;
    }
}
inline int scanf(int &ans)
{
    bool b=false;//判断正负号
    char in;
    while((in=getchar())!=EOF&&(in>'9'||in<'0')&&in!='-') ;//最数的第一个字符
    if(in==EOF)//结束输入
    return 0;
   else if(in=='-') {b=true;ans=0;}//是负号
    else
    ans=in-'0';//正数的最高位数字
    while((in=getchar())!=EOF,in>='0'&&in<='9')//输入还没有输完的数
            ans=ans*10+in-'0';
        return 1;
}
int Prim(int m)//最小生成树的prim算法的优化，可省时间
{
    int min,tm=m,t=1;//t 为s集合中点的个数
    s[m]=1; sum=0;
    for(int k=2;k<=n;k++)
    {
        min=INF;
        for(int i=1;i<=n;i++)
        if(s[i]==0)
        {
            if(node[i]>map[tm][i])
            node[i]=map[tm][i];
            if(min>node[i])
            {
                min=node[i]; m=i;
            }
        }

        if(s[m]==0)
        {
            t++; s[m]=1; sum+=min; tm=m;
        }
    }
    if(t==n)//s集合中有n个点，全部的点都在一棵树上
    return 1;
    return 0;
}
int main()
{
    int a,b,p,m,k,t,tt,aa[505];
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d%d",&n,&m,&k);
        set();//设制初始化
        while(m--)
        {
            scanf(a); scanf(b); scanf(p);
            if(map[a][b]>p)//判断重边
            map[a][b]=map[b][a]=p;
        }
        while(k--)
        {
            scanf(t);
            for(int i=1;i<=t;i++)
                scanf(aa[i]);
            for(int i=1;i+1<=t;i++)//只要把这些点连成一条线就可以了，因为每次只最一个最小的
            map[aa[i]][aa[i+1]]=map[aa[i+1]][aa[i]]=0;
        }
        t=Prim(1);
        if(t==1)
        printf("%d\n",sum);
        else
        printf("-1\n");
    }
}