Aiuto per Cammino minimo (mincammino2)

Aiuto
1

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:

#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!

2

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

3

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

#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;
	
}
4

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.

5

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

1 Mi Piace
6

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:

    • using ll = long long;
    • using pill = pair<int, ll>;
    • using pll = pair<ll, ll>;
      Praticamente ogni volta che scrivi ll e’ come se scrivessi long long, quindi la dichiarazione della priority queue diventa
      priority_queue<pll, vector<pll>, greater<pll>> pq;

  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.