글 읽기 - 우선순위 큐에서 시간초과 해결은 했으나 고수님들께 문의드립니다.

wjddms206 7년 전 0

다익스트라를 사용해서 문제를 풀었습니다. (우선순위 큐 사용)

계속 시간초과만 났었습니다.

그러나 질문을 토대로 어찌어찌 AC받았지만 얻어걸린 느낌이 많아서 질문드립니다 !!

9번째 줄과 19번째 줄에 하이픈(-)을 안붙이면 시간초과가 나더라고요.

그 하이픈 때문에 시간초과가 났던거였어요.

하이픈을 붙이니까 통과되더라고요.

왜 그런지 알려주실 분 계시나요???

부족한 저에게 지식을 나눠주세요ㅠ-ㅠ

priority_queue<pair<int, int> > q;

q.push(make_pair(0, start));
dist[start] = 0;

while (!q.empty())
{
	int curNode = q.top().second;
	int curCost = -q.top().first;
	q.pop();

	for(int i=0; i<edge[curNode].size(); i++)
	{
		int nextCost = edge[curNode][i].second; // 가중치
		int nextNode = edge[curNode][i].first; // end point
		if (dist[nextNode] > curCost + nextCost)
		{
			dist[nextNode] = curCost + nextCost;
			q.push(make_pair(-dist[nextNode], nextNode));
		}
	}
}

onjo0127 7년 전 3

STL에서 제공하는 우선순위 큐는 Max Heap이어서 가장 큰 원소부터 큐에서 빠져나오게 됩니다.

그런데 다익스트라에서는 코스트가 가장 작은 원소를 꺼내는 게 유리하기 때문에 Min Heap을 이용해야 합니다.

그래서 Max Heap을 그대로 이용해서 원소에 -1을 곱해 Min Heap으로 바꾼 겁니다. -1을 곱하면 순서가 뒤집혀서 반대로 빠져나오니까요 ㅎㅎ

wjddms206 7년 전 1

onjo0127님

크 넘넘 대단하십니다. 감사합니다

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

문제

문제

출처

ICPC

우선순위 큐에서 시간초과 해결은 했으나 고수님들께 문의드립니다.

wjddms206 7년 전 0

onjo0127 7년 전 3

wjddms206 7년 전 1

onjo0127님

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말