글 읽기 - prim 알고리즘으로 풀었는데 틀렸습니다가 나오네요..

tjgy9023 5년 전 0

예제는 잘나오는데.. 다익스트라 처럼 하는데 이거는 누적되지 않게 짰는데

어디서 틀린걸까요..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class PrimMain {
	static int[] dist;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken())+1;
		int M = Integer.parseInt(st.nextToken());
		dist = new int[N];
		visited = new boolean[N];
		ArrayList<Edge>[] alists = new ArrayList[N];
		for(int i = 0 ; i < N; i ++) {
			alists[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < M; i ++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			alists[a].add(new Edge(b,w));
		}
		
		prim(alists);
		
		int k = 0;
		for(int i = 1; i < N ; i++) {
			k += dist[i];
		}
		System.out.println(k);
	}
	public static void prim(ArrayList<Edge>[] alist) {
		int startVertex = 1;
		
		PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.weigth - o2.weigth;
			}
		});
		
		for(int  i = 0; i < alist.length ; i++)
			dist[i] = Integer.MAX_VALUE;
		
		dist[startVertex] = 0;
	
		pq.add(new Edge(startVertex, dist[startVertex]));
		
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			int vertex = edge.vertex;
			
			if(visited[vertex]) continue;
			
			visited[vertex] = true;
			for(Edge e: alist[vertex]) {
				int destination = e.vertex;
				int layoverWeight = e.weigth;
				
				if(dist[destination] > layoverWeight) {
					dist[destination] = layoverWeight;
					pq.add(new Edge(destination, dist[destination]));
				}
			}
			
		}
	}
	
						
}
class Edge{
	int vertex;
	int weigth;
	public Edge(int vertex, int weigth) {
		super();
		this.vertex = vertex;
		this.weigth = weigth;
	}
	
}

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

문제

문제

출처

ICPC

prim 알고리즘으로 풀었는데 틀렸습니다가 나오네요..

tjgy9023 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말