글 읽기 - 이게 왜 메모리초과가 날까요

oiaxi 5년 전 0

통과하는 답이랑 아무리 비교해도 어느부분이 다른지를 모르겠어요 ㅠㅠ..

전체 어레이를 표현하지도 않았는데 왜 메모리가 초과될까요?

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <limits.h>
#include <cstdio>

using namespace std;



vector<pair<int,int> > con[20001];

//bool operator<(pair<int,int> a, pair<int,int> b){
//	
//	if(a.first == a.second) return a.second> b.second;
//	else return a.first> b.first;	
//}



vector<int> dijkstra(int start,int V){
	vector<int> d(V+1,INT_MAX);
	d[start] = 0;
	priority_queue<pair<int,int> > pq;
	
	pq.push(make_pair(start,0));
	
	while(!pq.empty()){
		int current = pq.top().first;
		int distance = -pq.top().second;	
		pq.pop();
		
		if(d[current] < distance) continue;
		for(int i=0; i<con[current].size(); ++i){
			int next = con[current][i].first;
			int nextDistance = con[current][i].second + distance;
			
			if(d[next]>=nextDistance){
				d[current] = nextDistance;
				pq.push(make_pair(next, -nextDistance));
			}
			
				
		}
	}
	return d;
	
}

int main(){
	int V, E, K;
	scanf("%d %d", &V, &E);    
    scanf("%d", &K);  

	for(int i =1; i<=E; ++i){
		int u,v,w;
		scanf("%d %d %d", &u, &v, &w);
		con[u].push_back(make_pair(v,w));
	}
	vector<int> d;
	d=dijkstra(K,V);
	
	for(int i=1; i<=V; ++i){
		d[i] == INT_MAX ? printf("INF\n") : printf("%d\n", d[i]);
	}
	
	return 0;	
}

djm03178 5년 전 1

다익스트라에서는 반드시 거리가 가까운 것을 먼저 우선순위 큐에서 빼야 합니다. 그런데 pair<int, int>는 항상 "first끼리 먼저 비교하고, first가 같은 경우에만 second를 비교"합니다. 이 코드에서는 정점 번호를 first에 넣었기 때문에 정점 번호를 먼저 비교하게 되고, 이 번호에는 아무런 의미가 없으므로 불필요하게 정점들이 계속 우선순위 큐에 잘못 들어가고 잘못된 순서로 나오게 됩니다. 거리를 first에 넣어야 합니다.
39번째 줄, 거리가 갱신될 때에만 우선순위 큐에 넣는 것이 좋습니다. 갱신되지 않고 같은 경우에는 넣는 것이 불필요합니다.

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

문제

문제

출처

ICPC

이게 왜 메모리초과가 날까요

oiaxi 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말