글 읽기 - 프림으로 구현했는데 어디서 시간 초과가 발생할까요?

w22ee1 7년 전 0

안녕하세요.

MST를 만드는데, 가장 큰 cost를 mc에 저장하고

가중치의 합에서 mc를 빼는 방식입니다.

어디서 시간초과가 나는걸까요?

import java.util.*;

class Edge{
	int next,cost;
	Edge(int n,int c){
		next = n;
		cost = c;
	}
	Edge(){
		next = 0;
		cost = 0;
	}
}

public class Main {

	Scanner sc;
	int n,m;
	ArrayList<Edge> g[] = new ArrayList[100010];

	void input(){
		sc = new Scanner(System.in);
		n = sc.nextInt();	m = sc.nextInt();

		for(int i = 1; i <= n; i++)
			g[i] = new ArrayList<Edge>();

		for(int i = 0; i < m; i++){
			int a = sc.nextInt();	int b = sc.nextInt();
			int c = sc.nextInt();

			g[a].add(new Edge(b,c));
		}

	}

	void process(){

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>(new Comparator<Edge>() {
			public int compare(Edge o1, Edge o2) {
				return o1.cost-o2.cost;
			}
		});

		boolean check[] = new boolean[100010];

		for(int i = 0; i < g[1].size(); i++){
			pq.add(g[1].get(i));
		}
		
		check[1] = true;

		int ans = 0;
		int mc = 0;


		while(!pq.isEmpty()){
			Edge p = pq.remove();
			if( check[p.next] )	continue;
			
			check[p.next] = true;
			
			ans += p.cost;
			
			if( mc < p.cost )
				mc = p.cost;
			
			int x = p.next;
			
			for(Edge ee : g[x]){
				pq.add(ee);
			}
		}

		System.out.println(ans - mc);

	}

	void output(){

	}

	public static void main(String args[]){
		Main m = new Main();

		m.input();
		m.process();
		m.output();
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

프림으로 구현했는데 어디서 시간 초과가 발생할까요?

w22ee1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말