Aiuto per Cammino minimo (mincammino2)

Aiuto
1

Salve gente! Ho bisogno di aiuto per risolvere il problema Cammino minimo.

Ho cercato di implementare l’algoritmo di Djikstra ma tranne per i casi d’esempio non riesce a risolvere nessun subtask.
Nello specifico il 2° e 3° subtask falliscono eccedendo il tempo d’esecuzione, il 4° riesce ad eseguirli entro il tempo ma da un output errato in quasi tutti i casi, e il 5° un misto.
Sto sbagliando qualcosa?

Ecco il mio codice:

#include <vector>
#include <set>
#include <algorithm>
#include <limits>
#include <climits>
using namespace std;

const long long INFINITY = LLONG_MAX;

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D) {
    set<int> Q;

    fill(D.begin(), D.end(), INFINITY);
    D[0] = 0;
    
    for (int i = 0; i<N; i++) 
        Q.insert(i);

    while (not Q.empty()) {
        bool boom = true;
        for (int num : Q) {
            if (D[num]!=INFINITY) {
                boom = false;
                break;
            }
        }
        if (boom) break;
        
        long long u = INFINITY;
        int ind = 0;
        for (int num : Q) {
            if (u>D[num]) {
                u = D[num];
                ind = num;
            }
        }
        Q.erase(ind);
        
        for (int i = 0; i<M; i++) {
            if (X[i]==ind) {
                int alt = D[ind]+P[i]; 
                if (alt<D[Y[i]]) 
                    D[Y[i]] = alt;
            }
        }
    }
    
    for (int i = 0; i<N; i++){
        if (D[i]==INFINITY) D[i]=-1;
    }
    
    return;
}

Grazie mille in anticipo!

2

Le risposte sbagliate sono dovute a un overflow (te lo lascio cercare), ma ci sono problemi molto più profondi.
Attualmente il tuo programma esegue in tempo \mathcal{O}(N^2+NM): considerando che in media un online judge esegue 10^8 operazioni in un secondo questo vuol dire che coi limiti correnti puoi stimare un tempo di esecuzione di circa 1 ora, molto più del secondo e mezzo che hai a disposizione.
Ti faccio notare che:

  • è completamente inutile scorrere la lista degli archi ogni volta che devi aggiornare le distanze
  • esistono modi più veloci di scorrere tutti i nodi di trovare quello a distanza minima

Se non sei familiare con questo genere di argomenti ti consiglio di guardare la lezione sui grafi presente su algobadge.

1 Mi Piace
3

Grazie! Ho risolto l’overflow e sono riuscito a risolvere il 4° subset.

Si potrebbe creare da subito un vettore per ogni nodo che indichi quali archi partono da esso in modo da non dover scorrere ogni volta X.

Gli darò un occhiata :upside_down_face: