글 읽기 - C++ priority queue 질문입니다.

simm4256 6년 전 1

다익스트라 문제에서 pq의 설정에 따라 아래처럼 답이 맞거나 틀립니다.

첫 번째는 pq의 노드를 pair<int,int>로 설정했고 그에 따라 compare 함수로 greater<pair<int,int>>를 사용했습니다.

두 번째는 pq의 노드를 커스텀 struct로 설정했고 operator< 를 오버로딩하여 min heap을 구현했습니다.

아무리 생각해도 두 코드의 차이점을 모르겠네요 ㅠㅠ

//틀린 답
#include <bits/stdc++.h>
#define p(a,b) pair<int,int>((a),(b))
using namespace std;

int v, e, k, a, b, c, cnt, dist[20001];
vector<pair<int, int>> edge[20001];
vector<pair<int, int>>::iterator it;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pair<int,int> x;

int main() {
	cin >> v >> e >> k;
	int i, j;
	for (i = 0; i < e; i++) {
		scanf("%d %d %d", &a, &b, &c);
		edge[a].push_back(p(b, c));
	}
	pq.push(p(k,0));
	while (!pq.empty()) {
		x = pq.top();
		pq.pop();
		if (dist[x.first]) continue;
		dist[x.first] = x.second;
		for (it = edge[x.first].begin(); it != edge[x.first].end(); it++) {
			if (dist[it->first] || it->first == k) continue;
			pq.push(p(it->first,it->second + x.second));
		}
	}
	for (i = 1; i <= v; i++) {
		if (!dist[i] && i != k) printf("INF\n");
		else printf("%d\n", dist[i]);
	}
}

/*====================================================*/

//맞는 답
#include <bits/stdc++.h>
#define p(a,b) pair<int,int>((a),(b))
using namespace std;

struct node {
	int first, second;
};

bool operator<(node a, node b) {
	return a.second > b.second;
}

int v, e, k, a, b, c, cnt, dist[20001];
vector<pair<int, int>> edge[20001];
vector<pair<int, int>>::iterator it;
priority_queue<node> pq;
node x;

int main() {
	cin >> v >> e >> k;
	int i, j;
	for (i = 0; i < e; i++) {
		scanf("%d %d %d", &a, &b, &c);
		edge[a].push_back(p(b, c));
	}
	pq.push(node{ k,0 });
	while (!pq.empty()) {
		x = pq.top();
		pq.pop();
		if (dist[x.first]) continue;
		dist[x.first] = x.second;
		for (it = edge[x.first].begin(); it != edge[x.first].end(); it++) {
			if (dist[it->first] || it->first == k) continue;
			pq.push(node{ it->first,it->second + x.second });
		}
	}
	for (i = 1; i <= v; i++) {
		if (!dist[i] && i != k) printf("INF\n");
		else printf("%d\n", dist[i]);
	}
}

kajebiii 6년 전 1

greator<int, int>로 정의하였을때

priority_queue에서 pi의 우선순위는

first를 먼저 비교하고, first가 같다면 second를 비교하여 알려줍니다.

즉, 틀린답의 코드는 first를 먼저 비교하는 연산자를 이용하고 있고,

맞는답의 코드는 직접 bool operator를 구현해주셔서 second를 먼저 비교하는 연산자를 이용하고 계십니다.

감사합니다.

simm4256 6년 전 1

정말 감사합니다.

pair의 비교 우선순위가 first부터임을 간과하고 있었네요..

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

문제

문제

출처

ICPC

C++ priority queue 질문입니다.

simm4256 6년 전 1

kajebiii 6년 전 1

simm4256 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말