글 읽기 - C++의 Priority Queue

dlqudrjs 4년 전 0

보통 C로 코딩을 하는데 이번에 C++ 라이브러리를 활용해보고자 연습겸 짰는데 계속 런타임 에러가 발생해서 질문드립니다.

PQ를 C로 구현해서 제출한 코드는 AC를 받았는데, PQ 라이브러리를 활용한 위 소스코드는 왜 안되는지 궁금합니다.

우선은 제 로컬에서 g++을 활용하였을때는 잘 동작했는데, 백준환경이 다른건지 아니면 제가 놓친게 있는건지 알고싶습니다.

#include<cstdio>
#include<queue>
#include<functional>
#include<stdlib.h>
#define IMAX 2147483647
using namespace std;
struct Node{
	int s,e, cost;
	Node(int s, int e, int cost) : s(s), e(e), cost(cost){}
};
struct cmp{
	bool operator()(Node a, Node b){
		return a.cost > b.cost;
	}
};
int compare(const void* a, const void* b){
	if(*(int*)a > *(int*)b) return 1;
	else if(*(int*)a < *(int*)b) return -1;
	else return 0;
}
int arr[2005][2005];
int dist[2005];
int dist_e[2005];
int ts[105];
int dijkstra(int*, int);
int n,m,t;
int s,g,h;
void pq_clear();
int main(){
	int T;
	int a,b,c;
	
	scanf("%d",&T);
	while(T--){
		scanf("%d %d %d",&n,&m,&t);
		scanf("%d %d %d",&s,&g,&h);
		s--;g--;h--;
		for(int i=0;i<n;i++){
			dist[i] = IMAX;
			dist_e[i] = IMAX;
			for(int j=0;j<n;j++){
				arr[i][j] = IMAX;
			}
		}
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&a,&b,&c);
			a--;b--;
			arr[a][b] = c;
			arr[b][a] = c;
		}
		dijkstra(dist, s);
		for(int i=0;i<t;i++){
			scanf("%d",&a);
			ts[i] = a;
		}
		qsort(ts, t, sizeof(int), compare);
		for(int i=0;i<t;i++){
			int e = ts[i]-1;
			for(int j=0;j<n;j++) dist_e[j] = IMAX;
			dijkstra(dist_e, e);
			//printf("<%d == %d + %d + %d, %d == %d + %d + %d>\n",dist[e] ,dist[g] , dist_e[h], arr[g][h] ,dist[e], dist[h] , dist_e[g], arr[g][h]);
			if(dist[e] == dist[g] + dist_e[h] + arr[g][h] || dist[e]==dist[h] + dist_e[g] + arr[g][h]){
				printf("%d ",e+1);
			}
		}
		printf("\n");
	}
	return 0;
}
int dijkstra(int* cost, int cur){
	priority_queue<Node, vector<Node>, cmp> pq;
	cost[cur] = 0;
	char visited[2000][2000]={0,};
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			visited[i][j]=0;
		}
	}
	for(int i=0;i<n;i++){
		if(arr[cur][i]!=IMAX && !visited[cur][i]){
			pq.push(Node(cur,i,arr[cur][i]));
			cost[i] = arr[cur][i];
			visited[cur][i] = 1;
		}
	}
	while(!pq.empty()){
		int cur = pq.top().e;
		int pq_cost = pq.top().cost;
		for(int i=0;i<n;i++){
			if(arr[cur][i] != IMAX && !visited[cur][i] && cost[i] > cost[cur] + arr[cur][i]){
				cost[i] = cost[cur] + arr[cur][i];
				visited[cur][i] = 1;
				pq.push(Node(cur, i, cost[i]));
			}
		}
		pq.pop();
	}
	while(!pq.empty()) pq.pop();
}