글 읽기 - 정직한 Dijkstra...

dohyeokkim 8년 전 0

Dijkstra에서 priority queue를 짤 때 어떤 stl container를 쓰는 것이 가장 좋을까요?

priority_queue는 nth element update가 안 돼서... googling해서 다음과 같은 답변을 참고했는데요.

http://stackoverflow.com/questions/649640/how-to-d...

그 중 조금 더 구현이 쉬워 보이는 2번째 방법이 좋을 거 같아 set을 이용했는데 TLE네요.

혹시 erase가 문제인가요?

#include <cstdio>
#include <utility>
#include <climits>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int main(){
	int v, e, k, a, b, w;
	int dist[20001] = {0};
	priority_queue<pair<int, int>> PQ;
	vector<vector<pair<int, int>>> edges;
	
	scanf("%d %d\n%d", &v, &e, &k);
	edges.resize(v + 1);

	for (int i = 1; i <= v; i++){
		if (i == k)
			dist[i] = 0;
		else
			dist[i] = INT_MAX / 2;

		PQ.push(make_pair(dist[i], i));
	}

	while (e--){
		scanf("%d %d %d", &a, &b, &w);
		edges[a].push_back(make_pair(b, w));
	}

	while (!PQ.empty()){
		int d, u, v, w;

		do{
			tie(d, u) = PQ.top();
			PQ.pop();
		} while (d != dist[u]);

		for (vector<pair<int, int>>::iterator i = edges[u].begin(); i!= edges[u].end(); i++){
			tie(v, w) = *i;
			if (d + w < dist[v]){
				dist[v] = d + w;
				PQ.push(make_pair(dist[v], v));
			}
		}
	}

	for (int i = 1; i <= v; i++){
		if (dist[i] != INT_MAX / 2)
			printf("%d\n", dist[i]);
		else
			puts("INF");
	}

	return 0;
}

koosaga 8년 전 1

find(PQ_dist.begin(), PQ_dist.end(), make_pair(dist[v], v))

이 부분은 O(N)이고 여기서 TLE입니다. find() 함수는 선형 탐색으로 구현되어 있기 때문입니다. 빠르게 원소 검색를 하려면, PQ_dist.find() 나 PQ_dist.lower_bound() 같은 거를 사용해야"만" 합니다.

그리고 개인적으로 priority_queue를 쓰는 것을 추천드립니다. std::set하고 order가 똑같고 / 일반적으로 훨씬 빠르며 / set보다 문제될 일이 적습니다. (set은 다루다 실수하면 왜 틀린지도 모르고 망하기 좋아서.. 저것도 좋은 실수의 예네요.)

ntopia 8년 전 0

보통 많이 쓰는 방법이 저 답변에서의 1번 방법 입니다.

ntopia 8년 전 0

priority_queue 를 그냥 쓰면

priority 가 높은것 = 값이 큰 것

부터 꺼내지게 됩니다

그래서 djikstra가 아닌 다른 요상한 짓을 하는 것으로 생각 됩니다

직접 간단한 예제를 만들어서 테스트 해보세요

ntopia 8년 전 0

그리고 맨 처음에는 priority_queue 에 시작점의 값만 넣어주는 것이 맞습니다

dohyeokkim 8년 전 0

주신 조언 다 적용해서 성공했습니다. 감사합니다.

생각해보니 거리가 무한대인 vertices를 다 넣어줄 필요가 없네요.

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

문제

문제

출처

ICPC

정직한 Dijkstra...

dohyeokkim 8년 전 0

koosaga 8년 전 1

ntopia 8년 전 0

dohyeokkim 8년 전 0

dohyeokkim 8년 전 0

dohyeokkim 8년 전 0

ntopia 8년 전 0

ntopia 8년 전 0

dohyeokkim 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말