Aiuto per Cammino minimo (mincammino2)

[AlessandroSicignano]

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

Ho implementato un Dijkstra con l’uso di una priority queue e non riesco a capire perché continua a fallire gli ultimi 4 testcase per TLE.

Ecco il mio codice:

#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <limits>

using namespace std;

using arco = pair<long long, int>; //peso, dest
using nodo = vector<arco>;

void mincammino(int N, int M, vector<int> X, vector<int> Y, vector<int> P, vector<long long>& D) {
    vector<nodo> grafo(N);
    for (int i = 0; i < M; i++)
        grafo[X[i]].emplace_back(P[i], Y[i]);
    std::fill(D.begin(), D.end(), -1);
    D[0] = 0;
    priority_queue<arco, vector<arco>, greater<arco>> q;
    q.emplace(0, 0);
    while (!q.empty())
    {
        int idx_u = q.top().second;
        q.pop();
        for (const arco& i : grafo[idx_u])
        {
            long long& D_v = D[i.second], D_u = D[idx_u];
            if (D_v == -1 || D_v > D_u + i.first)
            {
                D_v = D_u + i.first;
                q.emplace(D_v, i.second);
            }
        }
    }
}

Grazie mille in anticipo!

[Malmo]

Ciao!
Il tuo codice va in TLE perché la tua implementazione di Dijkstra non controlla se un nodo è già stato visitato prima di controllare i suoi vicini.

Esempio

Nell’esempio

5 5
0 1 1
0 2 5
1 3 10
2 3 5
3 4 10

il tuo codice itererà due volte sui vicini del nodo 3. Questo è perché il nodo 3 verrà inserito due volte nella priority_queue, una prima volta mentre si sta visitando il nodo 1, e nuovamente mentre si sta visitando il nodo 2 dato che, passando da esso, il percorso è più breve.
Questo tuttavia fa sì che il idx_u sia uguale a 3 per due iterazioni del ciclo while, cosa superflua visto che la prima iterazione è sufficiente a trovare potenziali percorsi minimi passanti dal nodo 3.

Come spiegato qui nel primo paragrafo questo porta la complessità da O(Nlog(M)+Mlog(M)) a O(NM) che, viste le assunzioni del problema, spiega il perché dei TLE.
Per risolvere dovrebbe essere sufficiente cambiare le prime linee del ciclo while a:

        int idx_u = q.top().second;
        long long dist_u=q.top().first;
        q.pop();
        if(D[idx_u]!=dist_u){
            continue;
        }

Questo perché se dist_u è diverso da D[idx_u], questo vuol dire che, dopo che la coppia {dist_u, idx_u} è stata inserita nella priority_queue, è stato trovato un percorso più breve per arrivare al nodo idx_u e, dato che la priority_queue mette in cima le coppie con la distanza minore, la coppia contenente il percorso più breve è già stata considerata. Di conseguenza, il nodo idx_u è già stato visitato ed i suoi vicini controllati in cerca di potenziali nuovi percorsi minimi

[AlessandroSicignano]

Risolto, grazie mille.