60/100 in "Sentieri Bollenti"

Aiuto
1

Punteggio: 60/100
Testcase:
Cattura
Sorgente:

 #include<stdio.h>
 #include<stdlib.h>

int vet[100], primo= 0, ultimo = 0, grafo[101][101], minimi[101], N;

void push(int x);

int pop();

bool empty();

int BFS();


int main() {
	FILE *f = fopen("input.txt", "r");
	int A, B;
	fscanf(f, "%d%d%d", &N, &A, &B);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			grafo[i][j] = -1;
	for (int i = 0, x, y; i < A; i++) {
		fscanf(f, "%d%d", &x, &y);
		grafo[x][y] = grafo[y][x]= 0;
	}
	for (int i = 0, x, y; i < B; i++) {
		fscanf(f, "%d%d", &x, &y);
		grafo[x][y] = grafo[y][x] = 1;
	}
	fclose(f);
	f = fopen("output.txt", "w");
	minimi[1] = 0;
	for (int i = 2; i <= N; i++)
		minimi[i] = 100;
	push(1);
	fprintf(f, "%d", BFS());
	fclose(f);
	system("PAUSE");
	return 0;
}

int BFS() {
	int nodo;
	while (!empty()) {
		nodo = pop();
		for (int i = primo; i < ultimo; i = (i + 1) % 100)
			fprintf(stderr, "%d ", vet[i]);
		fprintf(stderr, "\n");
		for (int i = 1; i <= N; i++)
			if (grafo[nodo][i] != -1 && minimi[nodo] + grafo[nodo][i] < minimi[i]) {
				minimi[i] = minimi[nodo] + grafo[nodo][i];
				push(i);
				for (int i = primo; i < ultimo; i = (i + 1) % 100)
					fprintf(stderr, "%d ", vet[i]);
				fprintf(stderr, "\n");
			}
	}
	return minimi[N];
}

void push(int x){
	bool trovato = false;
	for (int i = primo; i < ultimo && !trovato; i = (i + 1) % 100)
		if (vet[i] == x) {
			trovato = true;
			fprintf(stderr, "%d: doppione\n", x);
		}
	if (!trovato) {
		vet[ultimo] = x;
		ultimo = (ultimo + 1) % 100;
	}
}

int pop(){
	primo = (primo + 1) % 100;
	return vet[(primo - 1) % 100];
}

bool empty() {
	return primo == ultimo;
}

(Sul correttore online andrebbe compilato in C++ anche se è C perchè ho usato i bool)
So che non è efficientissimo ma pensavo andasse almeno :disappointed_relieved:

2

Ciao, il problema sta nell’implementazione della coda, ti consiglio di usare una std::queue ma preferisci usare il C dovresti aumentare le dimensioni dell’array dove lo allochi. Comunque nel C il tipo di dato bool viene definito nell’header <stdbool.h>.

2 Mi Piace
3

Grazie mille, con una coda lunga 100 dà 100/100! Ero convinto che, evitando di mettere in coda due volte lo stesso elemento, bastasse una coda di 100 per 100 nodi, ma una coda completamente piena immagino dia un falso positivo a empty(). (Non capisco perchè con una lunga 101 mi dia 70/100 però…)

4

Giusto, grazie del consiglio