Aiuto per Cammino minimo (mincammino2)

[DigitalDungeonsAndDa]

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

Sto provando a implementare un classico Djikstra, ho consultato il “Competitive programmer’s handbook” e lì ho trovato delle linee di codice che ho provato ad usare nel problema, modificandole un po’ perché se no al computer non piacevano, per un motivo o per l’altro. Dopo qualche oretta, sono arrivato al seguente codice:

#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D)
{
    vector<char> processed(N);// Per non dover usare vector<bool> (uso S per true ed N per false)
    queue<pair<long long int, long long int>> q{}; 
    vector<pair<long long int, long long int>> adj(M);
    vector<long long int> distanze(N);
    // Costruisco la adjacency list
    for (int i{ 0 }; i < M; ++i)
    {
        int nodoInizio{ X[i] };
        adj[nodoInizio] = { Y[i], P[i] };
    }
    // Costruisco il vettore delle distanze utilizzando un numero grosso
    // e il vettore per capire se un nodo è stato processato
    for (int i{ 0 }; i < N; ++i)
    {
        distanze[i] = 9000000000000000000;
        processed[i] = 'N';
    }
    distanze[0] = 0;
    q.push({ 0, 0 });
    while (!q.empty())
    {
        long long int a = q.front().second; // Nel CPH "q.front" era "q.top"... Mi ci è voluto un po' per capirlo
        q.pop();
        if (processed[a] == 'S')
            continue;
        processed[a] = 'S';
        for (auto u : adj[a]) // Il problema sta in questa riga
        {
            int b{ u.first };
            int w{ u.second };
            if (distanze[a] + w < distanze[b])
            {
                distanze[b] = distanze[a] + w;
                q.push({ -distanze[b], b });
            }
        }
    }
    fill(D.begin(), D.end(), distanze);

Il problema è che Visual Studio mi dice che nel ciclo for verso la fine del mio codice “questa istruzione ‘for’ basata sull’intervallo richiede una funzione “begin” appropriata, ma non ne è stata trovata alcuna” (E2291). Non ho la più pallida idea di cosa significhi, e ovunque ficco questo fantomatico begin il compiler trova un nuovo modo di dirmi che c’è qualcosa che non funge. Ho capito cosa sto cercando di fare con quel loop (considerare tutti gli archi che partono dal vertice a), ma non mi viene in mente un altro modo di farlo, e non riesco a correggere questo. Tra l’altro ho promesso ai miei compagni di specializzarmi sui grafi in vista delle olinfo a squadre e presentarsi senza nemmeno riuscire ad implementare Djikstra in un problema da mezza stellina sarebbe veramente imbarazzante… XD Qualcuno mi può illuminare, per favore?

Grazie mille in anticipo!

[frakkiobello]

Ciao, innanzitutto il codice è parecchio confusionario e secondo me avrebbe senso, una volta risolto l’errore in cui ti stai imbattendo, andare anche a migliorare il resto del codice soprattutto considerando che sono concetti parecchio diffusi quelli che stai implementando. Se ti servirà una mano nessun problema con calma facciamo tutto

Il problema è come crei le liste di adiacenza. Quello che vorremmo è che adj[i] contenga tutti i vicini (e le relative informazioni) del nodo i. Il nodo i può avere più di un vicino, per questo motivo usiamo una lista. adj[i] sarà una lista (nel tuo caso di tipo vector<pair<int, long long>>). Avendo N nodi necessitiamo di N di questo tipo di liste.
La dichiarazione corretta diventa dunque
vector<vector<pair<int, long long>>> adj(N);

In pratica abbiamo creato N liste inizialmente vuote, che riempirai man mano in questo modo:

adj[nodoInizio].push_back({ Y[i], P[i] });

Nella tua versione invece di avere N liste, avevi un’unica lista di grandezza M (anche ammettendo il tuo errore sarebbe dovuto essere N invece di M) e memorizzavi un unico vicino per ogni nodo.

Quando poi provavi ad iterare su adj[a] con for (auto u : adj[a]) il compilatore ti faceva notare che per come l’avevi dichiarata adj[a] non era una lista ma un singolo elemento, quindi non sapeva come iterarla (nello specirfico non trovava la funzione .begin() che indica l’inizio della lista).

Risolto questa parte avrai altri errori, secondo me il fatto che provi a risolverlo tu è propedeutico, quindi il mio aiuto si ferma qui per il momento, se poi non ne vieni comunque a capo allora chiedi nuovamente aiuto senza problemi.

[DigitalDungeonsAndDa]

Grazie mille! E io che pensavo che la lista fosse una… Non ci ho capito proprio niente ci continuerò a lavorare domani, se tutto va bene poi pubblico il codice della risoluzione (e magari mi decido se usare l’italiano o l’inglese )

[DigitalDungeonsAndDa]

Ciao di nuovo! Ora il mio codice ottiene 40 su 100, quindi suppongo di stare facendo progressi grazie al tuo suggerimento! Ho aggiunto un sacco di linee di commento, perché terrò questo file come appunti personali, ma ci sono dei passaggi che mi rimangono ancora oscuri (ed inoltre mi irrita assai il non aver ottenuto un punteggio pieno), quindi mi rivolgo di nuovo all’esperto!

Qui c’è il nuovo codice:

#include <vector>
#include <algorithm>
#include <queue>
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 int, long long int>>> listeDiAdiacenza(N);
    // Le liste di adiacenza sono il modo di rappresentare un grafo su C++.
    // Ad ogni nodo corrisponde una lista.
    // Nel caso dell'algoritmo di Djikstra, il grafo da analizzare è pesato sugli archi.
    // Ogni lista quindi contiene delle coppie formate da due numeri, che rappresentano degli archi.
    // Il primo numero corrisponde al nodo di arrivo di un arco, il secondo al suo peso.
    // Possono esistere liste vuote e liste con più elementi.
    // Il numero totale di liste è N, il numero dei nodi,
    // mentre il numero totale di elementi nelle liste è M, il numero degli archi.

    queue<pair<long long int, long long int>> q{};
    // Questa è una "priority queue",
    // ossia una lista di elementi legati da relazioni di precedenza,
    // come una fila di persone in un negozio.
    // Serve per considerare solo gli archi necessari per la risoluzione del problema,
    // risparmiando quindi tempo.

    vector<char> nodoProcessato(N);
    // Questo vettore serve per "far ricordare" al computer
    // quali nodi sono già stati processati.
    // Uso i char per non usare un vettore di bool
    // (potrebbe comportarsi in modi inaspettati altrimenti).

    vector<long long int> distanze(N);
    // In questo vettore si trovano le distanze d[i] dal nodo 0 al nodo i.

    // Questo ciclo 'for' serve per costruire le liste di adiacenza.
    for (int i{ 0 }; i < M; ++i)
    {
        long long int nodoConsiderato{ X[i] };
        // Questo ciclo deve iterare una volta per ogni elemento nel vettore X.
        // X è inizializzato da 0 a M-1, quindi i deve iterare da 0 a M-1.

        listeDiAdiacenza[nodoConsiderato].push_back({ Y[i], P[i] });
        // Non ho idea se potrebbe funzionare anche con qualcosa del tipo:
        // listeDiAdiacenza[X[i]].push_back({ Y[i], P[i] });
        // A scanso di pericoli esplicito X[i] come variabile int, così sono sicuro che funzioni.
    }
    // Quello che ottengo con questo ciclo è un numero N di liste di adiacenza
    // contenenti un numero totale di M coppie, che rappresentano il mio grafo.

    // Con questo ciclo impongo le distanze dal nodo 0 agli altri nodi come infinite.
    // Mi serve perché Djikstra opera comparando le distanze di diversi percorsi:
    // se un percorso per arrivare ad un nodo è minore della distanza assegnata a tale nodo,
    // L'algoritmo la sostituisce con la nuova distanza del percorso trovato.
    for (int i{ 0 }; i < N; ++i)
    {
        distanze[i] = 9223372036854775807;
        // Ci dev'essere un modo più furbo di farlo...
    }

    // Con questo ciclo dico al computer che non abbiamo ancora processato alcun nodo.
    for (int i{ 0 }; i < N; ++i)
    {
        nodoProcessato[i] = 'N';
        // N sta per No, S sta per Sì, e rispondono alla domanda "i è un nodoProcessato?"
        // ... Almeno, nella mia testa funziona così XD
    }

    distanze[0] = 0;
    // La distanza del nodo di partenza da sé stesso è sicuramente 0.

    q.push({ 0, 0 });
    // A quanto ho capito, nella priority queue gli elementi in coda sono
    // delle coppie di numeri, determinate nel seguente modo:
    // il primo numero è il nodo di cui voglio analizzare i vicini,
    // il secondo è la sua distanza dal nodo di partenza.

    // Adesso si entra nel cuore di Djikstra:
    // Questo tratto di algoritmo serve per calcolare le distanze minime di tutti i nodi dal nodo 0.
    while (!q.empty())
    {
        long long int a = q.front().first;
        // a è il nodo di cui voglio analizzare i vicini (non trovo un nome furbo da dargli).

        q.pop();
        // Devo cancellare l'elemento che sto analizzando, proprio come
        // quando una persona in coda viene servita, poi esce dal negozio.
        // (In questo caso a quanto pare esplode, ma non è un mio problema.)

        if (nodoProcessato[a] == 'S')
            continue;
        // Se ho già analizzato un nodo, non serve analizzarlo di nuovo.
        // Questo è il grande pregio dell'algoritmo di Djikstra.

        nodoProcessato[a] = 'S';
        // Una volta finito con i vicini di a, potrò dire di averlo processato:
        // Quindi, tanto vale dirlo subito.

        // Non ho idea di come funzioni questo particolare ciclo for, ma quello che fa è
        // considerare tutti gli elementi della lista di adiacenza corrispondente al nodo a.
        for (auto arcoConsiderato : listeDiAdiacenza[a])
        {
            long long int nodoArrivo{ arcoConsiderato.first };
            // Bisogna ricordare che l'arco considerato è una pair<int, int>,
            // il cui primo elemento è il numero del nodo di arrivo
            // ed il secondo è il peso dell'arco che li collega.

            long long int pesoArco{ arcoConsiderato.second };

            if (distanze[a] + pesoArco < distanze[nodoArrivo])
            {
                distanze[nodoArrivo] = distanze[a] + pesoArco;
                // Se l'arco che sto considerando riduce la distanza tra il nodo 0 ed il
                // nodo di arrivo dell'arco, sostituisco quella distanza nel vettore delle distanze,
                // nella posizione che corrisponde al nodo di arrivo dell'arco.

                q.push({ nodoArrivo, -distanze[nodoArrivo] });
                // Per finire, aggiorno la priority queue:
                // ogni volta che una persona esce dal negozio, tutti i vicini
                // che hanno subito una modifica alla loro distanza entrano.
                // Tra questi, considererò solo quelli che non ho ancora considerato (eeew che schifo di frase),
                // e darò la precedenza al nodo con la distanza minore tra quelli in coda:
                // infatti, sicuramente non esiste un percorso più breve per arrivare a lui,
                // siccome usando Djikstra si assume che non esistono archi dal peso negativo.
                // Da notare come le distanze dei nodi sono salvate come il loro opposto:
                // questo perchè la priority queue dà la precedenza a valori maggiori,
                // mentre io voglio dare precedenza ai valori minori.
                // Questo è un modo elegante di risolvere il problema.
            }
        }
    }

    // Concludo il problema inserendo le distanze finali nel vettore della soluzione.
    for (int i{ 0 }; i < N; ++i)
    {
        D[i] = distanze[i];

        if (distanze[i] == 9223372036854775807)
            D[i] = -1;
    }
}

Grazie mille per la pazienza!!

[frakkiobello]

Per ottenere punteggio pieno manca poco, però rinnovo il mio invito alla semplificazione del codice una volta ottenuto punteggio pieno, ti do quindi l’ultima dritta che ti serve e poi quando hai risolto mi permetto di darti altri suggerimenti.

L’idea di base è corretta e i commenti che hai lasciato fanno intuire che hai capito il ragionamento, rimane però un errore.

@DigitalDungeonsAndDa

queue<pair<long long int, long long int>> q{};
    // Questa è una "priority queue",

In realtà no, quella non è una priority queue bensi una coda standard ( una semplice queue). La differenza è che le code memorizzano gli elementi in base all’ordine in cui vengono inseriti (in particolari sono strutture chiamate FIFO (First-In, First-Out)), Se per esempio in una coda di interi provi a inserire i valori 3, 1, 4 quando li toglierai otterrai gli elementi nello stesso ordine 3, 1, 4. Quello che vorremmo noi è però una struttura che ordini gli elementi che inseriamo dal più piccolo al più grande (ossia vorremmo togliere i valori in ordine 1, 3, 4). Per farlo dobbiamo usare una priority_queue, nel nostro caso: priority_queue<pair<long long, int>> pq, l’unica accortezza è che una coda con priorità ti restituisce gli elementi “dal più grande al più piccolo”, mentre noi vorremmo analizzarli dal più piccolo (dal nodo più vicino) al più grande (a quello più lontano).
Per farlo dobbiamo usare questa sintassi priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; con la quale specifichi

• Il tipo degli elementi pair<long long, int>
• Il contenitore usato dietro le quinte vector<pair<long long, int>>
• E il modo in cui confrontare i vari elementi greater<pair<long long, int>>, ossia che ordiniamo gli elementi dal più vicino al più distante e a parità di distanza scegliamo prima quello con indice minore (anche se quest’ultima parte è irrilevante)

Attento che devi mettere come primo elemento la distanza e come secondo elemento l’indice del nodo, altrimenti non stai ordinando in maniera corretta.

Inoltre cambia leggermente la sintassi: la .front() ora si chiama .top()

Prova a seguire questo consiglio e dimmi se riesci a ottenere 100/100.

[DigitalDungeonsAndDa]

Ho finalmente ottenuto 100/100! Ora però sono curioso di sapere come pulire e semplificare il mio codice, siccome è ancora piuttosto… Artigianale, ecco. Ad esempio, mi sembra inverosimile doversi ricordare il valore massimo di un long long e sicuramente avrei potuto costruire le liste di adiacenza ed i vettori delle distanze e dei nodi processati in un unico ciclo. Comunque sia, il tuo aiuto è stato preziosissimo! Grazie ancora!

Ecco il codice della mia soluzione, nel caso qualcun altro incappi nei miei stessi dubbi:

#include <vector>
#include <algorithm>
#include <queue>
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, int>>> listeDiAdiacenza(N);
    // Le liste di adiacenza sono il modo di rappresentare un grafo su C++.
    // Ad ogni nodo corrisponde una lista.
    // Nel caso dell'algoritmo di Djikstra, il grafo da analizzare è pesato sugli archi.
    // Ogni lista quindi contiene delle coppie formate da due numeri, che rappresentano degli archi.
    // Il primo numero corrisponde al nodo di arrivo di un arco, il secondo al suo peso.
    // Possono esistere liste vuote e liste con più elementi.
    // Il numero totale di liste è N, il numero dei nodi,
    // mentre il numero totale di elementi nelle liste è M, il numero degli archi.

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq{};
    // Questa è una "priority queue", ossia una lista di elementi
    // legati da relazioni di precedenza, come una fila di persone in un negozio.
    // Serve per considerare solo gli archi necessari per la risoluzione del problema,
    // risparmiando quindi tempo. Con questa sintassi, inoltre, specifico che 
    // deve venire data la precedenza alla coppia con il minor numero come primo elemento.

    vector<char> nodoProcessato(N);
    // Questo vettore serve per "far ricordare" al computer quali nodi sono già stati processati.
    // Uso i char per non usare un vettore di bool
    // (potrebbe comportarsi in modi inaspettati altrimenti).

    vector<long long int> distanze(N);
    // In questo vettore si trovano le distanze d[i] dal nodo 0 al nodo i.

    // Questo ciclo 'for' serve per costruire le liste di adiacenza.
    for (int i{ 0 }; i < M; ++i)
    {
        int nodo{ X[i] };
        // Questo ciclo deve iterare una volta per ogni elemento nel vettore X.
        // X è inizializzato da 0 a M-1, quindi i deve iterare da 0 a M-1.

        listeDiAdiacenza[nodo].push_back({ Y[i], P[i] });
        // Non ho idea se potrebbe funzionare anche con qualcosa del tipo:
        // listeDiAdiacenza[X[i]].push_back({ Y[i], P[i] });
        // A scanso di pericoli esplicito X[i] come variabile int, così sono sicuro che funzioni.
    }
    // Quello che ottengo con questo ciclo è un numero N di liste di adiacenza
    // contenenti un numero totale di M coppie, che rappresentano il mio grafo.

    // Con questo ciclo impongo le distanze dal nodo 0 agli altri nodi come infinite.
    // Mi serve perché Djikstra opera comparando le distanze di diversi percorsi:
    // se un percorso per arrivare ad un nodo è minore della distanza assegnata a tale nodo,
    // L'algoritmo la sostituisce con la nuova distanza del percorso trovato.
    for (int i{ 0 }; i < N; ++i)
    {
        distanze[i] = 9223372036854775807;
        // Ci dev'essere un modo più furbo di scrivere il massimo valore di un long long...
        // Qualche comando che non conosco?
    }

    // Con questo ciclo dico al computer che non abbiamo ancora processato alcun nodo.
    for (int i{ 0 }; i < N; ++i)
    {
        nodoProcessato[i] = 'N';
        // N sta per No, S sta per Sì, e rispondono alla domanda "i è un nodoProcessato?"
        // ... Almeno, nella mia testa funziona così XD
    }

    distanze[0] = 0;
    // La distanza del nodo di partenza da sé stesso è sicuramente 0.

    pq.push({ 0, 0 });
    // Nella priority queue gli elementi in coda sono
    // delle coppie di numeri, determinate nel seguente modo:
    // il primo numero è la distanza del nodo di cui voglio analizzare i vicini dal nodo 0,
    // il secondo è il numero corrispondente a quel nodo.

    // Adesso si entra nel cuore di Djikstra:
    // Questo tratto di algoritmo serve per calcolare le distanze minime di tutti i nodi dal nodo 0.
    while (!pq.empty())
    {
        int nodoA = pq.top().second;
        // A è il nodo di cui voglio analizzare i vicini.

        pq.pop();
        // Devo cancellare l'elemento che sto analizzando, proprio come
        // quando una persona in coda viene servita, poi esce dal negozio.
        // (In questo caso a quanto pare esplode, ma non è un mio problema.)

        if (nodoProcessato[nodoA] == 'S')
            continue;
        // Se ho già analizzato un nodo, non serve analizzarlo di nuovo.
        // Questo è il grande pregio dell'algoritmo di Djikstra.

        nodoProcessato[nodoA] = 'S';
        // Una volta finito con i vicini di A, potrò dire di averlo processato:
        // Quindi, tanto vale dirlo subito.

        // Non ho idea di come funzioni questo particolare ciclo for, ma quello che fa è
        // considerare tutti gli elementi della lista di adiacenza corrispondente al nodo A.
        for (auto arcoAB : listeDiAdiacenza[nodoA])
        {
            long long nodoB{ arcoAB.first };
            // Bisogna ricordare che l'arco considerato è una pair<int, int>,
            // il cui primo elemento è il numero del nodo di arrivo (B)
            // ed il secondo è il peso dell'arco che li collega.

            long long pesoArco{ arcoAB.second };

            if (distanze[nodoA] + pesoArco < distanze[nodoB])
            {
                distanze[nodoB] = distanze[nodoA] + pesoArco;
                // Se l'arco che sto considerando riduce la distanza tra il nodo 0 ed il
                // nodo di arrivo dell'arco, sostituisco quella distanza nel vettore delle distanze,
                // nella posizione che corrisponde al nodo di arrivo dell'arco.

                pq.push({ distanze[nodoB], nodoB });
                // Per finire, aggiorno la priority queue:
                // ogni volta che una persona esce dal negozio, tutti i vicini
                // che hanno subito una modifica alla loro distanza entrano.
                // Tra questi, considererò solo quelli che non sono ancora stati processati,
                // e darò la precedenza al nodo con la distanza minore tra quelli in coda:
                // infatti, sicuramente non esiste un percorso più breve per arrivare a lui,
                // siccome usando Djikstra si assume che non esistono archi dal peso negativo.
            }
        }
    }

    // Concludo il problema inserendo le distanze finali nel vettore della soluzione.
    for (int i{ 0 }; i < N; ++i)
    {
        D[i] = distanze[i];

        if (distanze[i] == 9223372036854775807)
            D[i] = -1;
    }
}

[frakkiobello]

Ben fatto per il 100/100!

Per quanto riguarda i suggerimenti che ti anticipavo:

• Includendo la libreria #include <bits/stdc++.h> includi praticamente tutte le altre librerie che ti servono per il competitive programming.
• Puoi usare praticamente sempre l’operatore = invece delle graffe
• Non so a cosa ti riferisci quando dici che i bool possono comportarsi in modi inaspettati onestamente, usa i bool senza problemi
• Invece di usare i valore massimo dei long long hai due opzioni principali. La prima (quella più sicura) è utilizzare -1 per indicare che un nodo non è ancora stato raggiunto. La seconda consiste nell’usare un valore molto grande ma che non deve necessariamente essere il più grande possibile per il tipo che stai usando, spesso si usa 1e9 (che corrisponde a 1000000000) per gli int e 2e18 (che corrisponde a 2000000000000000000 per i long long)

Seguendo le indicazioni che ti ho dato dovrebbe uscirti qualcosa di simile

#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, int>>> listeDiAdiacenza(N);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq{};
    vector<bool> nodoProcessato(N, false);
    vector<long long int> distanze(N, 2e18);
    for (int i = 0; i < M; ++i) {
        listeDiAdiacenza[X[i]].push_back({ Y[i], P[i] });
    }

    distanze[0] = 0;
    pq.push({ 0, 0 });
    while (!pq.empty()) {
        int nodoA = pq.top().second;
        pq.pop();
        if (nodoProcessato[nodoA])
            continue;
        nodoProcessato[nodoA] = true;
        for (auto arcoAB : listeDiAdiacenza[nodoA]) {
            long long nodoB = arcoAB.first;
            long long pesoArco = arcoAB.second ;
            if (distanze[nodoA] + pesoArco < distanze[nodoB]) {
                distanze[nodoB] = distanze[nodoA] + pesoArco;
                pq.push({ distanze[nodoB], nodoB });
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        D[i] = distanze[i];
        if (distanze[i] == 2e18)
            D[i] = -1;
    }
}

Inoltre volendo non è nemmeno necessario utilizzare nodoProcessato, puoi usare direttamente il vettore distanze

[DigitalDungeonsAndDa]

Grazie mille, tutto chiaro! Avevo visto un articolo riguardo ai vettori di bool che affermava che siccome non sono veri e propri contenitori, usarli potrebbe portare a risultati imprevisti, ma probabilmente si riferiva a programmi più complicati di quelli che dovrò usare per le olinfo.