글 읽기 - 최단경로 자바풀이 질문합니다. 틀린케이스입니다

lhgwoo2 7년 전 0

9퍼에서 틀렸습니다.

코드를 살펴볼 때 이론상으로는 이상이 없다고 생각하는데

혹시 제가 놓치는 부분이 있는지 도움부탁드립니다.

코드 첨부하겠습니다!

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

//힙을 사용한 빠른 다익스트라
public class Main {
	static int INF = 1000000;
	
	static class Compare implements Comparator<Point>{

		@Override
		public int compare(Point o1, Point o2) {
			return Integer.compare(o1.cost, o2.cost);
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		ArrayList<Point>[] a = new ArrayList[n+1];
		int d[] = new int[n+1];
		boolean check[] = new boolean[n+1];
		
		for(int i=1;i<=n;i++){
			a[i] = new ArrayList<>();
			d[i] = INF;
		}
		
		for(int i=0;i<m;i++){
			int s = sc.nextInt();
			int e = sc.nextInt();
			int c = sc.nextInt();
			
			a[s].add(new Point(e, c));
		}
		
		Compare cmp = new Compare();
		PriorityQueue<Point> q = new PriorityQueue(cmp);
		
		d[k]=0;
		q.add(new Point(k, 0));
		while(!q.isEmpty()){
			Point p = q.poll();
			
			if(check[p.end])continue;
			check[p.end]=true;
			
			for(int i=0;i<a[p.end].size();i++){
				Point temp = a[p.end].get(i);
				if(d[temp.end]>d[p.end]+temp.cost){
					d[temp.end]=d[p.end]+temp.cost;
					q.add(new Point(temp.end, -d[temp.end]));
				}
			}
		}
		
		for(int i=1;i<=n;i++){
			if(d[i]>=INF)System.out.println("INF");
			else System.out.println(d[i]);
		}
		
	}

}
class Point{
	int end;
	int cost;
	
	Point(int end, int cost){
		this.end = end;
		this.cost = cost;
	}
}

lhgwoo2 7년 전 0

아 해결했습니다......
PQ에서 비교 값을 minheap로 해놨는데 MAXheap으로 착각해서 거리 데이터 값을 음수로 바꿔넣어주어 계속적인 오류였습니다.

저같은 실수 하시는 분 참고되셨으면 좋겠네요.ㅋ

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

문제

문제

출처

ICPC

최단경로 자바풀이 질문합니다. 틀린케이스입니다

lhgwoo2 7년 전 0

lhgwoo2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말