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?
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.
"
Se tu dichiari la priority queue come : priority_queue< pair< int , int > , vector <pair < int, int > >, greater < pair<int , int > > > non hai quel problema.
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?
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.
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?