글 읽기 - 27% 정도에서 틀렸다고 나오네요.

csm0626 6년 전 0

제 머리로는 아무리 생각해도 예외적인 케이스를 찾기가 어렵네요.

고수님들 도와주세요,.. 소스는 아래와같습니다.

우선 초기 도시값이 1000000005라서, 방문하지 않았으니까 처음 방문하면 해당 도시를 출발점으로 하는

버스들을 우선순위퀴에 전부 밀어 넣은 다음에,

보거든요. 시작점은 city[startnode] = 0으로 무조건 잡습니다. (시작은 0이니까) 그 뒤에는

예외를 찾기힘들거다 어쨋든 출반은 시작에서 부터해서 queue에 전부담으니

하지만 27%에서, 틀렸습니가 뜨네요. 무슨이유일까요?

//city[s]는 0으로 셋팅됨
	private static void dijkstraSolution(ArrayList<Bus>[] busStops,int[] city,int s,int e){
		PriorityQueue<Bus> prior = new PriorityQueue<Bus>();
		prior.addAll(busStops[s]); //시작점을 우선 순위큐에 모두 넣고 돌린다.
		
		while(prior.size()!=0){//버스의 갯수가 10만개니까 10개를 다 봐야되지 않을까 싶다.
			Bus bus = prior.poll();
			if(city[bus.finishNode] == 1000000005){//안가본 애니까 넣는다.
				city[bus.finishNode] = city[bus.startNode] + bus.cost;
				prior.addAll(busStops[bus.finishNode]);
			}else{
				if(city[bus.finishNode] > city[bus.startNode] + bus.cost){
					city[bus.finishNode] = city[bus.startNode] + bus.cost;
				}
			}
		}
		
		System.out.println(city[e]);
	}

WeissBlume 6년 전 0

priority queue 는 어떤 값을 기준으로 삼아야 할까요?
`poll()`을 했을 때에 어떤 값이 나와야 할까요?

csm0626 6년 전 0

다익스트라가, 우선 bfs에서 착안된다점을 이해하지 못했습니다.

프림의 최소스패닝 그래프와 다르다는걸 이번에 알았습니다.

문제는 해결됐습니다. 답변주셔서 감사합니다.

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

문제

문제

출처

ICPC

27% 정도에서 틀렸다고 나오네요.

csm0626 6년 전 0

WeissBlume 6년 전 0

csm0626 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말