Spesa lampo signal error 11

Aiuto
1

Sto provando a risolvere https://training.olinfo.it/#/task/spesa/statement “spesa lampo” la mia idea iniziale era di usare dijkstra ma poi visto che i percorsi hanno tempo uguale ho usato una bfs visto che è un grafo non pesato.
La mia idea era quella di applicarla dal nodo 1 fino ai supermercati poi resettare tutto ma tenermi memorizzato quanti percorsi ho usato per i vari supermercati e poi applicarla di nuovo e quando visito un supermercato sommo i percorsi a quelli già trovati.

Il mio codice è questo qua:

     #include <bits/stdc++.h>
    using namespace std;

    ifstream in ("input.txt");
    ofstream out ("output.txt");

    queue<int> coda;
    bool visited[10005];
    int disti[10005];
    vector< vector < int > > g;
    bool v[10005];


    int main(){
        int n, m, k, a, b, counter=0, minn=100005;
        int minu[10005];

    	in >> n >> m >> k;

        g.resize(n);

    	for(int i=0; i<k; i++){
            in >> a;
            v[a] = true;
            minu[a] = 0;
    	}

    	for(int i=0; i<n; i++){
            in >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
    	}

    	a = 1;
    	coda.push(a);
    	visited[a] = true;

    	while(!coda.empty()){
            a = coda.front();
            coda.pop();

            for(int i=0; i<g[a].size(); i++){
                if(!visited[g[a][i]]){
                    visited[g[a][i]] = true;
                    coda.push(g[a][i]);
                    disti[g[a][i]] = disti[a] + 1;

                    if(v[g[a][i]]){
                        counter++;
                        minu[g[a][i]] = disti[g[a][i]];
                    }
                }
            }
            if(counter>=k)
                break;
    	}

    	for(int i=0; i<=n; i++){
            visited[i] = false;
    	}

    	for(int i=0; i<=n; i++){
            disti[i] = 0;
    	}

    	a = n;
    	coda.push(a);
    	visited[a] = true;
    	counter = 0;

    	while(!coda.empty()){
            a = coda.front();
            coda.pop();

            for(int i=0; i<g[a].size(); i++){
                if(!visited[g[a][i]]){
                    visited[g[a][i]] = true;
                    coda.push(g[a][i]);
                    disti[g[a][i]] = disti[a] + 1;
                    if(v[g[a][i]]){
                        counter++;
                        minu[g[a][i]] = minu[g[a][i]] + disti[g[a][i]];
                        if(minn>minu[g[a][i]])
                            minn = minu[g[a][i]];
                    }
                }
            }
            if(counter>=k)
                break;
    	}

        out << minn;

        in.close();
        out.close();
        return 0;
    }

Nella maggior parte dei testcase mi dà che il compilatore è triggerato perchè uso la memoria in modo losco (signal error 11), in alcuni output is not correct e l’ultimo me lo dà giusto.

Mi aiutereste a trovare l’errore?
Grazie in anticipo.

2

CIao! Il problema con la memoria lo hai perché i nodi partono da 1 fino ad N, mentre il resize di g l’hai fatto di n, quindi solo gli elementi da 0 a N-1.
I casi che ti vanno in output errato sono dovuti all’implementazione della bfs, infatti non puoi togliere e mettere gli elementi dallo stesso lato della coda, facendo così ti ritrovi che coda.front() contiene il nodo più distante.

3

Grazie mille ora provo a metterlo a posto

4

Ma con la struttura coda non tolgo già dalla cima e aggiungo elementi nuovi in fondo?
Se così non è, cosa molto probabile, potreste spiegarmi come si utilizza la coda e se c’è una struttura dati più adatta al mio scopo?
Grazie in anticipo

5

No scusami hai ragione :sweat_smile:, avevo in mente uno stack leggendo la tua soluzione non so perché.

6

Ok c’erano altri 2 errorini, trovabili con un po’ di debug: nel for in cui prendi gli archi hai scritto i<n anziché i<m e dopo aver completato la prima bfs coda non è per forza vuota (dovuto al break se counter>=k).
Scusami ancora per quella correzione errata, l’ho visto troppo di fretta.

7

Grazie mille non so perchè ho messo n, riguardo alla coda mi sono proprio scordato di settarlo;
grazie mille ancora perchè sarei stato giorni prima di trovare l’errore, grazie

8

Non so ho provato a correggere ma mi dà solo 10/100 non so perchè

    #include <bits/stdc++.h>
    using namespace std;

    ifstream in ("input.txt");
    ofstream out ("output.txt");

    queue<int> coda;
    bool visited[10005];
    int disti[10005];
    vector< vector < int > > g;
    bool v[10005];


    int main(){
        int n, m, k, a, b, counter=0, minn=100005;
    int minu[10005];

	in >> n >> m >> k;

    g.resize(n+1);

	for(int i=0; i<k; i++){
        in >> a;
        v[a] = true;
        minu[a] = 0;
	}

	for(int i=0; i<m; i++){
        in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
	}

	a = 1;
	coda.push(a);
	visited[a] = true;

	while(!coda.empty()){
        a = coda.front();
        coda.pop();

        for(int i=0; i<g[a].size(); i++){
            if(!visited[g[a][i]]){
                visited[g[a][i]] = true;
                coda.push(g[a][i]);
                disti[g[a][i]] = disti[a] + 1;

                if(v[g[a][i]]){
                    counter++;
                    minu[g[a][i]] = disti[g[a][i]];
                }
            }
        }
        if(counter>=k)
            break;
	}

	for(int i=0; i<=n; i++){
        visited[i] = false;
	}

	for(int i=0; i<=n; i++){
        disti[i] = 0;
	}
    for(int i=0; i<coda.size(); i++)
        coda.pop();
	a = n;
	coda.push(a);
	visited[a] = true;
	counter = 0;

	while(!coda.empty()){
        a = coda.front();
        coda.pop();

        for(int i=0; i<g[a].size(); i++){
            if(!visited[g[a][i]]){
                visited[g[a][i]] = true;
                coda.push(g[a][i]);
                disti[g[a][i]] = disti[a] + 1;
                if(v[g[a][i]]){
                    counter++;
                    minu[g[a][i]] = minu[g[a][i]] + disti[g[a][i]];
                    if(minn>minu[g[a][i]])
                        minn = minu[g[a][i]];
                }
            }
        }
        if(counter>=k)
            break;
	}

    out << minn;

    in.close();
    out.close();
    return 0;
}

Mi sbaglia circa metà dei testcase

9

Ho risolto grazie ho tolto il counter break e alla fine era quello che mi dava problemi anche se non ho capito molto bene il perchè, grazie ancore per avermi aiutato a trovare gli errori.

10

Allora il counter break dava errore perché non svuotava completamente la coda, nemmeno quel ciclo for, dato che coda.size() si aggiorna mano a mano che fai il pop(), quindi svuoti solo metà coda, meglio usare un while.

11

Ok ora ho capito grazie mille