글 읽기 - 메모리초과 어떻게 해결할까요..?

kdr06006 4년 전 0

쓴만큼 할당해서 썼는데 메모리초과네요

어떻게해야하나요?

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define _size 101

int N, M;
typedef struct Queue {
	int cur, cost, time;
}Q;
Q* heap;
int size, cap;
bool check[_size][10001];//도시,비용

typedef struct City {
	int cost, time;
}C;
C* city[_size][_size];
int Size[_size][_size], Cap[_size][_size];

inline void swap(Q& a, Q& b) { Q temp = a; a = b; b = temp; }

void Re(Q a)
{
	++size;
	if (size >= cap) {
		Q* Temp = (Q*)realloc(heap, sizeof(Q) * (cap += 10));
		heap = Temp;
	}
	heap[size - 1] = a;
}

void Rre(int idx1, int idx2, C a)
{
	++Size[idx1][idx2];
	if (Size[idx1][idx2] >= Cap[idx1][idx2]) {
		C* Tp = (C*)realloc(city[idx1][idx2], sizeof(C) * (Cap[idx1][idx2] += 10));
		city[idx1][idx2] = Tp;
	}
	city[idx1][idx2][Size[idx1][idx2] - 1] = a;
}

void up(int idx)
{
	if (idx == 0) return;
	int par = (idx - 1) / 2;
	if (heap[idx].time < heap[par].time) {
		swap(heap[idx], heap[par]);
		up(par);
	}
}

void down(int idx)
{
	int cha = idx, L = idx * 2 + 1, R = idx * 2 + 2;
	if (L<size && heap[cha].time>heap[L].time) cha = L;
	if (R<size && heap[cha].time>heap[R].time) cha = R;
	if (idx != cha) {
		swap(heap[idx], heap[cha]);
		down(cha);
	}
}

void Enqueue(Q a)
{
	Re(a);
	up(size - 1);
}

Q Dequeue()
{
	Q tmp = heap[0];
	heap[0] = heap[--size];
	down(0);
	return tmp;
}

int BFS()
{
	while (size) {
		Q Cur = Dequeue();
		if (Cur.cur == N) return Cur.time;
		if (check[Cur.cur][Cur.cost]) continue;
		check[Cur.cur][Cur.cost] = 1;

		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < Size[Cur.cur][i]; j++) {
				if (city[Cur.cur][i][j].cost > 0) {
					Q Next = { i,Cur.cost + city[Cur.cur][i][j].cost,Cur.time + city[Cur.cur][i][j].time };
					if (Next.cost <= M && !check[Next.cur][Next.cost]) Enqueue(Next);
				}
			}
		}
	}

	return -1;
}

int main(void)
{
	heap = (Q*)malloc(sizeof(Q));
	for (int i = 0; i < _size; i++) for (int j = 0; j < _size; j++) city[i][j] = (C*)malloc(sizeof(C));

	int T;
	scanf("%d", &T);
	while (T--) {
		memset(check, false, sizeof(check));
		memset(Size, 0, sizeof(Size));
		size = 0;

		int K, n1, n2, n3, n4;
		scanf("%d %d %d", &N, &M, &K);
		while (K--) {
			scanf("%d %d %d %d", &n1, &n2, &n3, &n4);
			Rre(n1, n2, { n3,n4 });
		}

		Enqueue({ 1,0,0 });
		int d = BFS();
		if (d == -1) puts("Poor KCM");
		else printf("%d\n", d);
	}

	free(heap);
	for (int i = 0; i < _size; i++) for (int j = 0; j < _size; j++) free(city[i][j]);
}

juhongkim2 4년 전 1

bfs를 돌릴때 중복방문 체크는 큐에 넣으면서 해야합니다

큐에서 빼면서 중복방문을 체크하면 제대로 체크가 안되는 경우가 생기고

중복된 점이 계속 큐에 들어가게 되면 런타임에러나 메모리초과가 나올 수 있습니다

kdr06006 4년 전 0

@juhongkim2

아 혹시나싶어서 그랬던건데 감사합니다!

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

문제

문제

출처

ICPC

메모리초과 어떻게 해결할까요..?

kdr06006 4년 전 0

juhongkim2 4년 전 1

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말