# Aiuto per Cammino minimo (mincammino2)

**URL:** <https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571>\
**Category:** Aiuto\
**Created:** [9 Aprile 2025, 8:35pm UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571 "2025-04-09T20:35:50Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![gabripizzorni](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gabripizzorni/32/2990_2.png) [@gabripizzorni](https://forum.olinfo.it/u/gabripizzorni)\
**Post date:** [9 Aprile 2025, 8:35pm UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571/1 "2025-04-09T20:35:50Z")

</div>

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Cammino minimo.

Ho provato a implementare Dijkstra con una coda di priorità ma il problema mi dà solo 20/100 e non riesco a capire dove sia sbagliato il codice perché è la prima volta che provo a fare Dijkstra.

Ecco il mio codice:

```cpp
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
#include <utility>
#include <bits/stdc++.h>
using namespace std;

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

	vector<vector<pair<int, int>>> lista(N);
	vector<bool> visited(N);
	
	for(int i=0; i<M; i++)
		lista[X[i]].push_back({Y[i], P[i]});
	
	D.resize(N);
	
	D[0]=0;
	visited[0]=false;
	for(int i=1; i<N; i++)
	{
		visited[i]=false;
		D[i]=LLONG_MAX;
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	
	pq.push({0,0});
	
	while(!pq.empty())
	{
		int nodo=pq.top().first;
		int dist=pq.top().second;
		pq.pop();
		
		for(auto i: lista[nodo])
		{
			if(dist+i.second<D[i.first])
			{
				D[i.first]=dist+i.second;
				pq.push({i.first, dist+i.second});
			}
		}
	}
	
	for(int i=0; i<N; i++)
		if(D[i]==LLONG_MAX)
			D[i]=-1;
	
}

```

Grazie mille in anticipo!

---

<div class="post-metadata">

**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\
**Post date:** [10 Aprile 2025, 4:09pm UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571/2 "2025-04-10T16:09:09Z")

</div>

Se i valori superano INT\_MAX allora ti servono i long long ovunque. In particolare ti mancano all’interno della priority queue

---

<div class="post-metadata">

**Author:** ![gabripizzorni](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gabripizzorni/32/2990_2.png) [@gabripizzorni](https://forum.olinfo.it/u/gabripizzorni)\
**Post date:** [10 Aprile 2025, 7:02pm UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571/3 "2025-04-10T19:02:08Z")

</div>

Ho provato a mettere lista e pq long long ma continua a darmi gli output sbagliati.

Aggiornamento: ho cambiato il codice guardando un po’ in giro e adesso mi dà tutti i testcase giusti tranne per gli ultimi che vanno in timeout.  
Sapete come si può ottimizzare? Grazie

```cpp
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
#include <utility>
#include <bits/stdc++.h>
using namespace std;

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

	vector<vector<pair<long long, long long>>> lista(N);
	vector<bool> visited(N);
		
	for(int i=0; i<M; i++)
	{
		lista[X[i]].push_back({Y[i], P[i]});
	}
	
	D.resize(N);
	
	D[0]=0;
	visited[0]=false;
	for(int i=1; i<N; i++)
	{
		visited[i]=false;
		D[i]=LLONG_MAX;
	}
	
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
	
	pq.push({0,0});
	
	while(!pq.empty())
	{
		int nodo=pq.top().first;
		long long dist=pq.top().second;
		pq.pop();
			
		for(auto i: lista[nodo])
		{
			if(dist+i.second<D[i.first])
			{
				D[i.first]=dist+i.second;
				pq.push({i.first, dist+i.second});
			}
		}
	}
	
	for(int i=0; i<N; i++)
		if(D[i]==LLONG_MAX)
			D[i]=-1;
	
}

```

---

<div class="post-metadata">

**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\
**Post date:** [11 Aprile 2025, 11:27am UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571/4 "2025-04-11T11:27:26Z")

</div>

Nella coda devi mettere prima la distanza. Ogni volta vuoi prendere quello con distanza minore mentre così come stai facendo prendi quello con indice minore quindi può andare in quadratico.

---

<div class="post-metadata">

**Author:** ![gabripizzorni](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gabripizzorni/32/2990_2.png) [@gabripizzorni](https://forum.olinfo.it/u/gabripizzorni)\
**Post date:** [11 Aprile 2025, 8:02pm UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571/5 "2025-04-11T20:02:06Z")

</div>

Ho provato e adesso mi fa tutti i testcase giusti, mi ero perso che il parametro di comparazione della pq è il primo, grazie mille.

---

<div class="post-metadata">

**Author:** ![LorenzoFrittoli](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lorenzofrittoli/32/2341_2.png) [@LorenzoFrittoli](https://forum.olinfo.it/u/LorenzoFrittoli)\
**Post date:** [16 Aprile 2025, 7:13pm UTC](https://forum.olinfo.it/t/aiuto-per-cammino-minimo-mincammino2/9571/6 "2025-04-16T19:13:47Z")

</div>

Mi permetto di darti qualche consiglio non richiesto che ho trovato comodo:

1. Puoi utilizzare i `#define` o, ancora meglio, gli `using` per accorciare il codice (in particolar modo la dichiarazione della priority queue). Riporto quelli che uso piu’ spesso:

2. Se ti serve prendere gli elementi di un pair in due variabili puoi usare la seguente notazione:  
`auto[a, b] = mypair;`  
Ad esempio, quando prendi i valori del nodo e della distanza dalla pq puoi usare:  
`auto[dist, node] = pq.top();`

3. Se hai un vettore / array / set / qualunque cosa su cui vuoi iterare puoi usare la seguente notazione:  
`for (auto x: V) {...}`  
che e’ equivalente a fare `for x in V: ...` su python.  
Se vuoi modificare gli elementi di V basta che aggiungi un `&`:  
`for (auto& x: V) {...}`  
questo e’ ad esempio utile per prendere l’input dei programmi:  
`for (auto& x: V) cin >> x;`

4. Per concludere volevo fare un piccolo chiarimento di dubbissima utilita’ sulla priority queue: tu giustamente dici che ordina “a partire dal primo”, ma piu’ nel dettaglio utilizza il comparatore che gli hai passato (ovvero `greater<pair<long long, long long>>`).  
In sostanza gli hai dato una funzione che, dati due pair, ti dice quale e’ “piu’ grande”.  
Il modo in cui li ordina e’ per il valore del primo e poi del secondo elemento (quindi `{2, 0} < {2, 1} < {3, 1}`), hence la pq e’ ordinata in questo modo.

Personalmente queste sono tante cose “non dette” che mi hanno aiutato tanto (e soprattutto mi hanno fatto sentire un figo quando le ho imparate), spero che possano esserti utili.