L'esempio è sbagliato ma su file e terminale è corretto (mincammino)

Aiuto
1

So che la soluzione è sbagliata perché usa troppa memoria e magari da anche output sbagliati, ma almeno l’esempio so che è corretto. Il codice che ho utilizzato è questo

using namespace std;

int MAX_N = 10000001;

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<int> &D) {
    bool visitato [N];
    D[0] = 0;
    visitato[0] = false;

    int matrice_di_adiacenza [N][N] = {0};

    for (int i=0; i<M; i++)
        matrice_di_adiacenza[X[i]][Y[i]] = P[i];


    for(int i = 1; i < N; i++)
        D[i] = MAX_N, visitato[i] = false;

    for(int contatore = 0; contatore < N-1; contatore++) {
        //TROVA IL PIU VICINO
        int peso_del_piu_vicino = MAX_N, indice_del_piu_vicino;
        for (int i=0; i<N; i++){
            if ( visitato[i] == false && D[i] < peso_del_piu_vicino)
                peso_del_piu_vicino = D[i], indice_del_piu_vicino = i;
        }
        visitato[contatore] = true;

        for (int v = 0; v < N; v++) {
            if ( visitato[v] == false &&
                matrice_di_adiacenza[indice_del_piu_vicino][v] != 0 &&
                D[indice_del_piu_vicino] != MAX_N &&
                D[indice_del_piu_vicino] + matrice_di_adiacenza[indice_del_piu_vicino][v] < D[v])
                D[v] = D[indice_del_piu_vicino] + matrice_di_adiacenza[indice_del_piu_vicino][v];
        }
    }

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

}

qualcuno sa perché potrebbe succedere??
Questo invece non succede con il secondo esempio, che mi viene segnato come corretto.
Grazie !

2

Il problema

I variable length array non sono nello standard di C++, qualunque codice che ne contenga è in definitiva in balia del compilatore che può praticamente scegliere cosa farci a scelta tra:

  • Rifiutarsi di compilare (per esempio clang++ fa così)
  • Compilarlo, e allora buona fortuna a sapere cosa succede perché in principio ogni compilatore può scegliere di implementare i variable length array nel modo che più gli piace.
  • Compilare solo le occorrenze che capitano in una linea dispari

In particolare, in questo caso g++ compila il tuo codice ma non inizializza la matrice. Per esempio, sulla mia macchina il tuo programma ha prodotto i seguenti output per il primo caso d’esempio.

0 32764
0 32767
0 32767
0 32766
0 32765

La soluzione

Fortunatamente C++ fornisce modi standard di creare matrici (cioè std::vector<std::vector<T>>).
I vantaggi sono i seguenti:

  1. Essendo standard tutti i compilatori devono implementarlo allo stesso modo, e, a meno di undefined behaviour, questo vuol dire che ogni esecuzione darà la stesso risultato, anche su macchine e compilatori diversi.
  2. L’oggetto viene allocato sull’heap, evitando fastidiosi stack overflow in locale.
1 Mi Piace