글 읽기 - 메모리 초과가 발생해서 질문드립니다.

ainch96 7년 전 0

dist[i][j] => i정점 까지의 비용을 j만큼 사용했을 때의 최단 거리

으로 잡고, 다익스트라 돌렸는데, 체점이 되다가

8% 정도에서 메모리 초과가 발생합니다.

어디서 발생하는지 잘 모르겠습니다.

아마 우선순위 큐에서 발생하는 것으로 생각 되는데, 감을 잘 못잡겠습니다.

예전에 kcm travel 이라는 문제도 동일한 방법으로 풀었는데, 그때는 class를 사용하는 대신 pair을 사용했는데 그것 때문일까요?

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

class pn{
public:
	int node,dist,cost;//현재 정점 , 현재 까지 이동한 거리 , 든 비용
	pn(int a,int b,int c):
		node(a),dist(b),cost(c){}
	bool operator>(const pn& b)const{
		return dist > b.dist;
	}
	/*bool operator<(const pn& b)const{
		return dist < b.dist;
	}*/
};

class ed{
public:
	int node,dist,cost;
	ed(int a,int b,int c):
		node(a),dist(b),cost(c){}
};

priority_queue < pn , vector < pn > , greater < pn > > pq;

const int N = 105;
const int K = 10005;
const int INF = 1000000007;
int dist[N][K];
int k,n,r;

vector < vector < ed > > adj;

int dijkstra(){
	for(int i=0;i<N;++i)
		for(int j=0;j<K;++j)
			dist[i][j] = INF;//(정점,비용)
	dist[1][0] = 0;
	pq.push(pn(1,0,0));
	//node , dist, cost
	while(!pq.empty()){
		pn now = pq.top();
		for(int i = 0;i<adj[now.node].size();++i){
			ed& next = adj[now.node][i];
			if(now.cost + next.cost > k)continue;
			if(dist[next.node][now.cost + next.cost] <= dist[now.node][now.cost]+next.cost)continue;
			dist[next.node][now.cost + next.cost] = dist[now.node][now.cost] + next.dist;
			pq.push(pn(next.node,dist[next.node][now.cost+next.cost],now.cost + next.cost));
		}
		pq.pop();
	}
	int ret = INF;
	for(int i=0;i<=k;++i){
		ret = min(ret,dist[n][i]);
	}
	if(ret==INF)return -1;
	else return ret;
}

int main(){
	scanf("%d%d%d",&k,&n,&r);
	adj.resize(n+1);
	for(int i=0;i<r;++i){
		int x,y,d,c;
		scanf("%d%d%d%d",&x,&y,&d,&c);
		adj[x].push_back(ed(y,d,c));
	}
	int ans = dijkstra();
	printf("%d\n",ans);
	return 0;
}

h0ngjun7 7년 전 0

코드를 조금 수정하여 다음과 같이 하면 맞출 수 있습니다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
 
class pn {
public:
    int node, dist, cost;
    pn(int a, int b, int c) : node(a), dist(b), cost(c) {}
    bool operator>(const pn& b)const {
        return dist > b.dist;
    }
};
 
class ed {
public:
    int node, dist, cost;
    ed(int a, int b, int c) :
        node(a), dist(b), cost(c) {}
};
 
priority_queue < pn, vector < pn >, greater < pn > > pq;
 
const int N = 105;
const int K = 10005;
const int INF = 1000000007;
int dist[N][K];
int k, n, r;
 
vector < vector < ed > > adj;
 
int dijkstra() {
    for (int i = 0; i < N; ++i) for (int j = 0; j < K; ++j) dist[i][j] = INF;
    dist[1][0] = 0;
    pq.push(pn(1, 0, 0));
    //node , dist, cost
    while (!pq.empty()) {
        pn now = pq.top(); pq.pop();
        if (dist[now.node][now.cost] < now.dist) continue;
        for (auto &next : adj[now.node]) {
            if (now.cost + next.cost > k)continue;
            if (dist[next.node][now.cost + next.cost] <= dist[now.node][now.cost] + next.dist)continue;
            dist[next.node][now.cost + next.cost] = dist[now.node][now.cost] + next.dist;
            pq.push(pn(next.node, dist[next.node][now.cost + next.cost], now.cost + next.cost));
        }
    }
    int ret = INF;
    for (int i = 0; i <= k; ++i) ret = min(ret, dist[n][i]);
    if (ret == INF) return -1;
    return ret;
}
 
int main() {
    scanf("%d%d%d", &k, &n, &r);
    adj.resize(n + 1);
    for (int i = 0; i<r; ++i) {
        int x, y, d, c;
        scanf("%d%d%d%d", &x, &y, &d, &c);
        adj[x].push_back(ed(y, d, c));
    }
    int ans = dijkstra();
    printf("%d\n", ans);
    return 0;
}

ainch96 7년 전 0

정말 감사드립니다 ㅠㅠ 그리고 저렇게 하면 시간도 줄어들겠네요 ㅠㅠ 정말 감사드립니다.... ㅠㅠ

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

문제

문제

출처

ICPC

메모리 초과가 발생해서 질문드립니다.

ainch96 7년 전 0

h0ngjun7 7년 전 0

ainch96 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말