# 60/100 in "Sentieri Bollenti"

**URL:** <https://forum.olinfo.it/t/60-100-in-sentieri-bollenti/5084>\
**Category:** Aiuto\
**Created:** [21 Marzo 2018, 4:50pm UTC](https://forum.olinfo.it/t/60-100-in-sentieri-bollenti/5084 "2018-03-21T16:50:28Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Volpe](https://forum.olinfo.it/user_avatar/forum.olinfo.it/volpe/32/500_2.png) [@Volpe](https://forum.olinfo.it/u/Volpe)\
**Post date:** [21 Marzo 2018, 4:50pm UTC](https://forum.olinfo.it/t/60-100-in-sentieri-bollenti/5084/1 "2018-03-21T16:50:28Z")

</div>

Punteggio: 60/100  
Testcase:

 ![Cattura](https://forum.olinfo.it/uploads/default/original/1X/1e69477df55c4bd918785c85fd496a2217c030e3.PNG)  
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 😥

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [21 Marzo 2018, 5:49pm UTC](https://forum.olinfo.it/t/60-100-in-sentieri-bollenti/5084/2 "2018-03-21T17:49:25Z")

</div>

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>`.

---

<div class="post-metadata">

**Author:** ![Volpe](https://forum.olinfo.it/user_avatar/forum.olinfo.it/volpe/32/500_2.png) [@Volpe](https://forum.olinfo.it/u/Volpe)\
**Post date:** [28 Marzo 2018, 3:54pm UTC](https://forum.olinfo.it/t/60-100-in-sentieri-bollenti/5084/3 "2018-03-28T15:54:15Z")

</div>

> [@bortoz](#):
>
> aumentare le dimensioni dell’array dove lo allochi

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ò…)

---

<div class="post-metadata">

**Author:** ![Volpe](https://forum.olinfo.it/user_avatar/forum.olinfo.it/volpe/32/500_2.png) [@Volpe](https://forum.olinfo.it/u/Volpe)\
**Post date:** [28 Marzo 2018, 3:56pm UTC](https://forum.olinfo.it/t/60-100-in-sentieri-bollenti/5084/4 "2018-03-28T15:56:05Z")

</div>

> [@bortoz](#):
>
> \<stdbool.h\>

Giusto, grazie del consiglio