Page 1 of 1

Gettin Memory Limit with BFS

Posted: Mon Jun 05, 2006 12:10 am
by Sotek
First of all sorry about mi English cause is not very good :)
I'm trying to solve the problem called "The mysterious X network", you can see it here: http://acmicpc-live-archive.uva.es/nuev ... php?p=3502

I'm using BFS but the judge doesn't accept the problem because of the memory usage (memory limit)
What i'm doing wrong ?

Thank you in advance :)

Code: Select all

#include <iostream>
#include <list>
#include <queue>
#include <stdio.h>

using namespace std;

typedef list<int> ListaNodos;
typedef list<int>::iterator ListaNodosIterador;

typedef struct dnodo {
 int nodo;
 int distancia;
} dnodo;

int main() {
	int casos, i, j, k, n, w, camarada, conoce, tio, inicio, fin;
	ListaNodos *C;
	ListaNodosIterador it;
	dnodo *actual, *tmp;
	scanf("%d", &casos);
	queue<dnodo *> Q;
	for(i=0; i<casos; i++) {
		// get input
		scanf("%d", &n);
		C = new ListaNodos[n];	
		for(j=0; j<n; j++) {
			scanf("%d", &camarada);
			scanf("%d", &conoce);
			for(k=0;k<conoce;k++) {
				scanf("%d", &tio);
				C[camarada].push_back(tio);
				C[tio].push_back(camarada);
			}
		}
		// get the start (inicio) and end (fin) node
		scanf("%d", &inicio);
		scanf("%d", &fin);		
		// BFS
		actual = new dnodo;
		actual->nodo=inicio;
		actual->distancia=0;
		Q.push(actual);
		while(1) {
			actual = Q.front();
			Q.pop();
			if(actual->nodo == fin) {
				while(!Q.empty()) {
					tmp = Q.front();
					delete tmp;
					Q.pop();
				}
                                // Print the solution
				printf("%d %d %d\n", inicio, fin, actual->distancia-1);
				break;
			}
			it=C[actual->nodo].begin();
			while(it != C[actual->nodo].end()) {
				w = *it;
				tmp = new dnodo;
				tmp->distancia = actual->distancia+1;
				tmp->nodo = w;
				Q.push(tmp);
				*it++;				
			}
			delete actual;
		}	
		for(j=0; j<n; j++) {
			C[j].clear();
		}
		delete[] C;
	}
	return 0;
}

Posted: Wed Jun 07, 2006 4:29 pm
by asif_rahman0
i think there is a problem in ur code which is QUEUE overflow.
so check ur code again or change the code again or use array instead of VECTOR. Then experiment with vector.
ok.
i did the same thing may be 1yr ago.
:)

Posted: Thu Jun 08, 2006 12:25 am
by Sotek
I've found the problem.
The queue got very big very soon because I did not check to expand a node just if it wasn't expanded previously.

Jus added this:

bool expandedNodes = new bool[n];

:)

Thank you for helping me asif_rahman0!

Posted: Thu Jun 08, 2006 8:56 am
by shamim
In general, many BFS code will get memory limit exceded because the actual solution isn't BFS at all.

There are some DP problems, which seems like BFS, but you must use DP.

Posted: Sun Jun 11, 2006 5:29 pm
by Sotek
ok shamim, thank you :)