Connect the Cities

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 701 Accepted Submission(s): 212

Problem Description

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.  

 

Input

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.

 

Output

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

 

Sample Input

16 4 31 4 22 6 12 3 53 4 332 1 22 1 33 4 5 6

 

Sample Output

1

 

Author

dandelion

 

Source

HDOJ Monthly Contest – 2010.04.04

 

Recommend

lcy

/*点多变少的时候用克利斯卡尔算法，点少边的时候用prim算法真心的心累，交了20几发卡时过的*/#include
     
      #define N 550#define INF 0x3f3f3f3fusing namespace std;/*********输入输出外挂************/template 
      
       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
       
        val)//判重边            {                mapn[x][y]=mapn[y][x]=val;            }        }        for(int i=0;i