글 읽기 - 틀린 테스트케이스를 알수 있을까요??

barcelonamessi 7년 전 0

다익스트라 알고리즘을 사용하였는데 틀린 이류를 잘 모르겠습니다

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;

public class A1753 {

	public static void main(String[] args) {
		int V;
		int E;
		int start_point;
		class point{
			int from;
			int to;
			int weight;
			point(){}
			point(int from, int to, int weight){
				this.from=from;
				this.to=to;
				this.weight=weight;
			}
		}
		class Get_Line implements Comparator<point>{

			@Override
			public int compare(point arg0, point arg1) {
				
				if(arg0.weight>arg1.weight)
					return 1;
				else if(arg0.weight<arg1.weight)
					return -1;
				return 0;
			}
			
			
		}
		
		Scanner scan=new Scanner(System.in);
		
		
		V=scan.nextInt();
		E=scan.nextInt();
		Vector<Vector<point>>arr=new Vector<Vector<point>>(E+1);
		start_point=scan.nextInt();
		Comparator<point> comparator=new Get_Line();
		PriorityQueue<point> p_queue=new PriorityQueue<point>(300001,comparator);
		 
		int count=0;
		int MAX=987654321;
		int[] len=new int[20001];
		boolean[] visit=new boolean[20001];
		for(int i=0; i<=V; i++){
			arr.add(new Vector<point>());
			len[i]=MAX;
			visit[i]=false;
		}
		for(int i=0; i<E; i++){
			int flag=0;
			int from=scan.nextInt();
			int to=scan.nextInt();
			int weight=scan.nextInt();
			point temp=new point(from,to, weight);
			
			for(int j=0; j<arr.get(from).size(); j++){
				if(arr.get(from).elementAt(j).to==to && arr.get(from).elementAt(j).weight>weight){
					arr.get(from).elementAt(j).weight=weight;
					flag=1;
					break;
				}else if(arr.get(from).elementAt(j).to==to && arr.get(from).elementAt(j).weight<=weight){
					flag=2;
					break;
				}
			}
			if(flag==2)
				continue;
			

			if(flag==0)
				arr.get(from).add(temp);
		}
		
		
		
		//primary queue 활용. 큐에 현재 포인트를 넣음
		len[start_point]=0;
		visit[start_point]=true; //방문했음.
		count++;
		for(int i=0; i<arr.get(start_point).size(); i++){
			p_queue.add(arr.get(start_point).elementAt(i));
			len[arr.get(start_point).elementAt(i).to]=arr.get(start_point).elementAt(i).weight;
			
		}
		while(!p_queue.isEmpty()){
			point cur=new point();
			
			
			cur=p_queue.peek();//가장 가까운것 가져옴.
			p_queue.remove();
			
			if(len[cur.to]<len[cur.from]+cur.weight){
				
				continue;
			}
			len[cur.to]=len[cur.from]+cur.weight;
			visit[cur.to]=true;
			count++;
			for(int i=0; i<arr.get(cur.to).size(); i++){//거리 업데이트
				
				point temp;
				temp=arr.get(cur.to).elementAt(i); // 새 노드.
				
				
				if(len[temp.to]>len[temp.from]+temp.weight){
				
					len[temp.to]=len[temp.from]+temp.weight;
					
					
				}
				p_queue.add(temp);
				
			//	System.out.println("from"+temp.from +"to"+temp.to+"weight"+temp.weight);
			}
			
			
			
		}
		
		for(int i=1; i<=V; i++){
			if(i==start_point)
				System.out.println(0);
			else if(len[i]==MAX){
				System.out.println("INF");
			}else{
				System.out.println(len[i]);
			}
		}
	
		
	}
	

}

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

문제

문제

출처

ICPC

틀린 테스트케이스를 알수 있을까요??

barcelonamessi 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말