Connect the Cities

/*点多变少的时候用克利斯卡尔算法，点少边的时候用prim算法真心的心累，交了20几发卡时过的*/#include<bits/stdc++.h>#define N 550#define INF 0x3f3f3f3fusing namespace std;/*********输入输出外挂************/template <class T>inline bool scan_d(T &ret){    char c;    int sgn;    if(c=getchar(),c==EOF)        return 0; //EOF    while(c!=‘-‘&&(c<‘0‘||c>‘9‘))        c=getchar();    sgn=(c==‘-‘)?-1:1;    ret=(c==‘-‘)?0:(c-‘0‘);    while(c=getchar(),c>=‘0‘&&c<=‘9‘)        ret=ret*10+(c-‘0‘);    ret*=sgn;    return 1;}inline void out(int x){    if(x>9)        out(x/10);    putchar(x%10+‘0‘);}/*********输入输出外挂************/int t;int n,m,k;int mapn[550][550];//用来构建图bool vis[550];//用来记录那个点访问过也就是判环用的int d[550];//表示选中的结点到当前结点的最小距离int x,y,val,q,rt[550];void init(){    memset(mapn,INF,sizeof mapn);    memset(vis,false,sizeof vis);    memset(d,INF,sizeof d);}int prim(int m){    int root;//表示当前选中的结点    int minn=INF;    root=m;    vis[m]=true;    long long cur=0;    int len=0;    for(int i=2;i<=n;i++)//优化的prim算法，总共要找n个点嘛，先找了m了，然后再找n-1个点就够了    {        minn=INF;        for(int j=1;j<=n;j++)//然后开始找点            if(!vis[j])//这个点没有遍历过            {                if(d[j]>mapn[root][j])                    d[j]=mapn[root][j];                if(minn>d[j])                {                    minn=d[j]; m=j;                }            }        if(!vis[m])//这个点没有遍历过        {            cur+=minn;            vis[m]=true;            root=m;            len++;        }    }    if(len==n-1)        return cur;    return -1;}int main(){    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    scan_d(t);    while(t--)    {        scan_d(n);scan_d(m);scan_d(k);        init();//初始化        for(int i=0;i<m;i++)        {            scan_d(x);scan_d(y);scan_d(val);            if(mapn[x][y]>val)//判重边            {                mapn[x][y]=mapn[y][x]=val;            }        }        for(int i=0;i<k;i++)        {            scan_d(q);            for(int j=0;j<q;j++)                scan_d(rt[j]);            /*既然已经联通了那么相互之间就不需要再花费钱去修路了*/            for(int j=0;j+1<q;j++)                    mapn[rt[j]][rt[j+1]]=mapn[rt[j+1]][rt[j]]=0;        }        printf("%d\n",prim(1));    }    return 0;}