7 - 10 도로 촌 촌 통 (30 분) 자바 버 전

이것 이 바로 가장 짧 은 길 입 니 다. 순 서 를 정 하고 start 와 end 를 찾 으 면 됩 니 다. c++ 로 하면 10 분 이면 끝 낼 수 있 을 것 같 습 니 다. 하지만 이번 학기 에 자바 를 배 우 겠 습 니 다. 자바 로 하 세 요. 너무 어렵 습 니 다. - "정적 동태"라 는 부분, 문맥 이...

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main{
	static class  node{                        //每一条路径
		int start,end;
		int cost;
		node(int x,int y){
			this.start = x;
			this.end = y;
		}
		node(int x,int y,int z){
			this.start = x;
			this.end = y;
			this.cost = z;
		}
	}
	static node f[] = new node[3010];
	static int n,m,cost;
	static int[] mark = new int[3010];
	private static void init(){
		for(int i=0;i<=n;i++){
			mark[i]=i;
		}
	}
	private static int getf(int x){
		if(mark[x]==x) return x;
		else{
			mark[x]=getf(mark[x]);
			return mark[x];
		}
	}
	private static int merge(int u,int v){
		int t1=getf(u);
		int t2=getf(v);
		if(t1==t2) return 0;
		else{
			mark[t1]=t2;
			return 1;
		}
	}

	public static void main(String[] args){
		Scanner in =new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		init();
		for(int i=1;i<=m;i++){
			int a=in.nextInt();
			int b=in.nextInt();
			int c=in.nextInt();
			f[i] =new node(a,b,c);
		}
		Arrays.sort(f,1,m+1,new Comparator() {
			@Override
			public int compare(node a,node b){
				if(a.cost1;i++){
			if(merge(f[i].start, f[i].end)==1){
				sum+=f[i].cost;
				cnt--;
				//System.out.println(cnt);
			}
		}
		//for(int i=1;i<=n;i++){
		//	System.out.println(getf(mark[i]));
		//}
		if(cnt==1) System.out.println(sum);
		else System.out.println(-1);
		in.close();
	}
	
	
}