# Cammino minimo 0/100

**URL:** <https://forum.olinfo.it/t/cammino-minimo-0-100/7299>\
**Category:** Aiuto\
**Created:** [26 Aprile 2022, 1:39pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299 "2022-04-26T13:39:41Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [26 Aprile 2022, 1:39pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/1 "2022-04-26T13:39:41Z")

</div>

Di recente ho provato a risolvere il problema cammino minimo.  
Ho provato esattamente in tre modi. Per prima cosa ho provato implementando Belman Ford, ma l’algoritmo era troppo lento. Dopo di che sono passato a Djikstra, notando che implementando Djikstra, il codice aveva ugualmente dei testcase errati. Dopo un analisi del problema sono arrivato a questo argomento, che dà ugualmente 0/100. Cosa sto sbagliando?

```auto
#include <vector>
#include<utility> 

using namespace std;

struct struttura{
	vector<pair<int, int>> collegamenti; 
	int entrata = 0; 
	bool passato = false; 
	bool collegatoazero = false; 
}; 

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {
	vector<struttura> nodo(N);
	pair<int, int> a; 
	nodo[0].collegatoazero = true; 
	for(int i = 0; i < M; i++){
		nodo[Y[i]].entrata++; 
		a.first = Y[i]; 
		a.second = P[i];  
		nodo[X[i]].collegamenti.push_back(a); 
		if(nodo[X[i]].collegatoazero) nodo[Y[i]].collegatoazero; 
	}
	
	int posizionetop = 0; 
	D[0] = 0; 
	while(posizionetop < N){
		
		for(int i = 0; i < N; i++){
			if(nodo[i].entrata == 0){
				for(int l = 0; l < nodo[i].collegamenti.size(); l++){
					//cout << i << " : i " << D[i] << " : COSTO I " << nodo[i].collegamenti[l].first << ": PEKO PAIN " << D[i] + nodo[i].collegamenti[l].second << " : COSTO"<< endl;
					nodo[nodo[i].collegamenti[l].first].entrata--;
					if(nodo[i].collegatoazero && (nodo[nodo[i].collegamenti[l].first].passato == false || D[nodo[i].collegamenti[l].first] > D[i] + nodo[i].collegamenti[l].second)){
						D[nodo[i].collegamenti[l].first]= D[i] + nodo[i].collegamenti[l].second; 
						nodo[nodo[i].collegamenti[l].first].passato = true; 
						nodo[nodo[i].collegamenti[l].first].collegatoazero = true; 
					}
				} 
				nodo[i].entrata = -1; 
				break; 
			}
		}
		posizionetop++; 
	}
	/*for(int i = 0; i < N; i++){
		cout << nodo[i].passato << endl; 
	}*/
	D[0] = 0; 
	for(int i = 1; i < N; i++) if(nodo[i].passato == false) D[i] = -1; 
}

```

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [26 Aprile 2022, 5:13pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/2 "2022-04-26T17:13:20Z")

</div>

Con Dijkstra funziona, riguardati come l’hai implementato.

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [27 Aprile 2022, 8:25am UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/3 "2022-04-27T08:25:10Z")

</div>

perfetto, vedrò di implementarlo nuovamente

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [27 Aprile 2022, 9:12am UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/4 "2022-04-27T09:12:22Z")

</div>

ti ringrazio, funziona, avevo sbagliato un passaggio nel codice, solo che ero stanco e non me n’ero accorto

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [2 Maggio 2022, 4:15pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/5 "2022-05-02T16:15:50Z")

</div>

una domanda ho implementato Djikstra in questo modo, cosa sbaglio?

```auto
#include <vector>

#include<utility>

#include<algorithm>

#include<climits>

#include<queue>

#define INT_MAX 2147483647

using namespace std;

struct struttura{

    priority_queue<pair<int, int>> collegamenti;

    int lunghezza = INT_MAX;

};

vector<struttura> nodi;

void Djikstra(int index, int N, vector<int> &D){

    while(!nodi[index].collegamenti.empty()){

       

        //cout << nodi[index].collegamenti.top().second << " ";

        if(D[nodi[index].collegamenti.top().second] > D[index] + nodi[index].collegamenti.top().first * -1){

           

            D[nodi[index].collegamenti.top().second] = D[index] + nodi[index].collegamenti.top().first * -1;

            Djikstra(nodi[index].collegamenti.top().second, N, D);

        }

        nodi[index].collegamenti.pop();

    }

}

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {

    nodi.resize(N);

    D.resize(N);

    pair<int, int> input;

    int i;

    for(i = 0; i < N; i++) D[i] = INT_MAX;

    for(i = 0; i < M; i++){

               

        input.second = Y[i];

        input.first = -1 * P[i];

        nodi[X[i]].collegamenti.push(input);

    }

   

    i = 0;

    D[0] = 0;

    //cout << " Arrivo qua " << endl;

    Djikstra(i, N, D);

    for(i = 0; i < N; i++){

        if(D[i] == INT_MAX) D[i] = -1;

    }

}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [2 Maggio 2022, 5:41pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/6 "2022-05-02T17:41:28Z")

</div>

Prova con questo input:  
5 7  
0 1 1  
0 2 1  
1 3 1  
2 1 1  
3 2 1  
3 4 1  
2 4 1

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [2 Maggio 2022, 5:42pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/7 "2022-05-02T17:42:17Z")

</div>

va bene fra poco provo, grazie dell’aiuto

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [2 Maggio 2022, 7:39pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/8 "2022-05-02T19:39:05Z")

</div>

ho provato a prendere 100/100 con quest’implementazione di Djikstra, ma non funziona ugualmente, prendo 20/100:

```auto
#include <vector>

#include<utility>

#include<algorithm>

#include<climits>

#include<queue>

#define INT_MAX 2147483647

using namespace std;

struct archi{

    int fine;

    int costo;

};

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {

    vector<archi> lista[N];

     

    D.resize(N);

    for(int i = 0; i < M; i++){

        archi in;

        in.fine = Y[i];

        in.costo = P[i];

        lista[X[i]].push_back(in);

        D[in.fine] = INT_MAX;

        D[X[i]] = INT_MAX;

    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push(make_pair(0, 0));  

    D[0] = 0;

    while(!pq.empty()){

        int nodo = pq.top().second;

        pq.pop();

        for(archi pross : lista[nodo]){

            if(D[pross.fine] > D[nodo] + pross.costo){

                D[pross.fine] = D[nodo] + pross.costo;

                pq.push(make_pair(D[pross.fine], pross.fine));

            }  

        }

    }

    for(int i = 0; i < N; i++){

        if(D[i] == INT_MAX) D[i] = -1;

    }

   

}

```

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [2 Maggio 2022, 8:02pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/9 "2022-05-02T20:02:26Z")

</div>

mincammino da 20/100 a tutti. Ho riprovato la mia soluzione che faceva 100/100 prima e ora fa solamente 20/100

---

<div class="post-metadata">

**Author:** ![Glauco](https://forum.olinfo.it/user_avatar/forum.olinfo.it/glauco/32/2371_2.png) [@Glauco](https://forum.olinfo.it/u/Glauco)\
**Post date:** [2 Maggio 2022, 8:07pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/10 "2022-05-02T20:07:01Z")

</div>

Io ho appena provato a sottoporre nuovamente la mia soluzione e prende 100

---

<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:** [2 Maggio 2022, 8:10pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/11 "2022-05-02T20:10:31Z")

</div>

> [@alenygam\_real](#):
>
> mincammino da 20/100 a tutti. Ho riprovato la mia soluzione che faceva 100/100 prima e ora fa solamente 20/100

Il task è stato aggiornato, sono stati aggiunti nuovi subtask e alcuni testcase sono stati modificati pertanto la tua soluzione potrebbe prendere un punteggio diverso.

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [2 Maggio 2022, 8:14pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/12 "2022-05-02T20:14:37Z")

</div>

scusatemi, ma il mio codice è un classicissimo dijkstra, non vedo per quale motivo non dovrebbe prendere punteggio pieno. Sbaglia completamente il 3 subtask…

```nohighlight
#include <bits/stdc++.h>

using namespace std;

struct arco {
	int fine;
	int peso;
};

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {
	vector<arco> list[N];
	D.resize(N);
	// Build adjacency list
	for (int i = 0; i < M; i++) {
		arco tmp;
		tmp.fine = Y[i];
		tmp.peso = P[i];
		list[X[i]].push_back(tmp);
		D[X[i]] = -1;
		D[tmp.fine] = -1;
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, 0));
	D[0] = 0;
	while (!pq.empty()) {
		int nodo = pq.top().second;
		pq.pop();
		for (arco next: list[nodo]) {
			if (D[nodo] + next.peso < D[next.fine] || D[next.fine] == -1) {
				D[next.fine] = D[nodo] + next.peso;
				pq.push(make_pair(D[next.fine], next.fine));
			}
		}
	}
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [2 Maggio 2022, 8:15pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/13 "2022-05-02T20:15:25Z")

</div>

Inizializza il vettore D[] in questo modo :

```
for(int i=0; i<N; i++) D[i] = INT_MAX;

```

altrimenti qualche distanza non viene inizializzata correttamente.  
la tua implementazione dell’algoritmo di Dijkstra salta la distanza in cima alla pq, pertanto devi considerare la distanza dist = pq.top().first e confrontarla con con i nodi adiacenti della lista.

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [2 Maggio 2022, 8:16pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/14 "2022-05-02T20:16:53Z")

</div>

Che babbo che sono. Ci tengo a precisare che questa era una svista e tutte le mie altre implementazioni di dijkstra erano corrette.

🤡

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [2 Maggio 2022, 8:20pm UTC](https://forum.olinfo.it/t/cammino-minimo-0-100/7299/15 "2022-05-02T20:20:10Z")

</div>

scherzavo, non funziona ancora…

Ok ora funziona… Mi ero dimenticato di inizializzarlo correttamente…