HDU3371（Connect the Cities）最小生成树

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3371

package D0816;
/*
 * 题目大意；连接城市。
 * 思路，将已经连接的城市之间置为0，求最小生成树。
 * */
import java.io.*;
public class HDU3371 {

	static int[][]map;
	static int[]dist;
	static int n,m,k;
	static int s = 1;
	
	public static void prime(){
		boolean[]p = new boolean[n+1];
		for(int i = 1;i<=n;i++){
			p[i] = false;
			if(s!=i)
				dist[i] = map[s][i];
		}
		p[s] = true;
		dist[s] = 0;
		
		for(int i = 1;i<=n;i++){
			int min = Integer.MAX_VALUE;
			int k = -1;
			for(int j = 1;j<=n;j++){
				if(!p[j] && dist[j]<min){
					min = dist[j];
					k = j;
				}					
			}
			if(k==-1)return;
			p[k] = true;
			for(int j = 1;j<=n;j++){
				if(!p[j]&&dist[j] > map[k][j])
					dist[j] = map[k][j];
			}
		}
	}
 	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		st.nextToken();
		int t = (int)st.nval;
		while(t-->0){
			st.nextToken();
			n = (int)st.nval;
			st.nextToken();
			m = (int)st.nval;
			st.nextToken();
			k = (int)st.nval;
			
			map = new int[n+1][n+1];
			
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
					if(i==j)map[i][j]=0;
					else
						map[i][j]=Integer.MAX_VALUE;
			dist = new int[n+1];
			
			int u,v,w;
			for(int i = 0;i<m;i++){
				st.nextToken();
				u = (int)st.nval;
				st.nextToken();
				v = (int)st.nval;
				st.nextToken();
				w = (int)st.nval;
				if(w<map[u][v])
					map[u][v] = map[v][u] = w;
			}
			int t1;
			while(k-->0){
				st.nextToken();
				t1 = (int)st.nval;
				int[]tmp = new int[t1+1];
				for(int i = 1;i<=t1;i++){
					st.nextToken();
					tmp[i] = (int)st.nval;
				}
				for(int i = 1;i<=t1;i++){
					for(int j = i+1;j<=t1;j++){
						map[tmp[i]][tmp[j]]=map[tmp[j]][tmp[i]] = 0;
					}
				}
			}
			prime();
			int sum = 0;
			int num = 0;
			for(int i = 1;i<=n;i++){
				if(dist[i]!=Integer.MAX_VALUE){
					sum+=dist[i];
					num++;
				}
			}
			if(num==n)//注意这个啊！！！！wa了n次，最小生成树种要有n个点，如果还存在有孤立的点就不能修路
				System.out.println(sum);
			else System.out.println(-1);
		}
	}

}