2 problemi nell'implementazione dijkstra

#1

https://pastebin.com/BxV2KBmd
Salve, sto provando in questi giorni a implementare l’algoritmo di dijkstra e ho trovato un pdf da cui ho preso spunto ma ci sono due problemi:
1 Non riesco a capire cosa succede in questa parte:
for (auto w : v[corrente]) {
if (distanze[corrente]+w.second < distanze[w.first]) {
distanze[w.first] = distanze[corrente]+w.second;
q.push({w.first,-distanze[w.first]});
}
}

2 Nel problema omonimo risolve solo due task, negli altri sfora il tempo, cosa devo migliorare nel problema?

Grazie mille in anticipo!

#2

-distanze[w.first] ?? ci metti il meno?

#3

Sì, perché il priority queue mette i valori più grandi all’inizio e mettendo il meno posso invertirlo, non so se mi sono spiegato, nel dubbio ti metto la spiegazione del pdf:
"A small difficulty is that in Dijkstra’s algorithm, we should find the node with the
minimum distance, while the C++ priority queue finds the maximum element as
default. An easy trick is to use negative distances, which allows us to directly use
the C++ priority queue.
"

#4

Se tu dichiari la priority queue come :
priority_queue< pair< int , int > , vector <pair < int, int > >, greater < pair<int , int > > > non hai quel problema.

#5

E poi posso usarla facilmente con un q.first e un q.second?

#6

Certo, l’unica differenza è che li ordina in modo crescente

#7

ok, grazie mille, lo userò.
Per il resto, hai qualche consiglio?

#8

Utilizza i long long int, altrimenti prendi wa.
Per il resto sembra ok.

#9

Wa?
Comunque, non credo sia quello il problema visto che per adesso totalizzo 10/100 in dijkstra

#10

WA significa wrong answer, quindi output errato:
Hai fatto qualche prova in locale per cedere se l’algoritmo fa effettivamente ciò che gli chiedi di fare?

#11

In locale, sì e poi riesco a risolvere due task, l’unico problema è che ci mette molto e non capisco perché, nel pdf leggo che invece è molto veloce

#12

Infatti dovrebbe esserlo, primo consiglia prova a riscriverlo meglio, senza i meno e a ripostare. Fra poco dovrei avere qualche minuto per leggere bene il codice.

#13

Allora provo subito!

#14

https://pastebin.com/ypk24xZv
15/100 ma stavolta i task che non risolvo mi dà output non corretto e non execution timed out

#15

Ho provato anche con long long ma non cambia nulla

#16

corrente=q.top().second;
…
if(distanze[corrente]+y.second<distanze[y.first]){
distanze[y.first]=distanze[corrente]+y.second;

Mi sbaglio o sommi le distanze con i nodi?

#17

Non mi sembra, y.second, che è uguale a v[].second, sono i pesi degli archi

#18

hai ragione scusa, ma forse il problema è che il testo tratta di un grafo diretto ma tu lo tratti come un grafo non diretto

v[a].push_back({b,c});
v[b].push_back({a,c});

togliendo il secondo push_back fa 95/100, se vuoi far 100/100 utilizza i consigli sui long long di @frakkiobello

#19

Ho guardato, modificato e provato il codice per 30 minuti senza accorgermene :smile:

#20

Grazie mille, ora posso stare più tranquillo sapendo usare dijkstra pero non capisco:da cosa nel testo si capisce che tratta di archi diretti? O forse è una condizione dell’algoritmo in sé che forse ho tralasciato?