Se poate raspunde cumva in O(1)? 

Tot respectul meu pentru voi toti, daca nu erati voi pot sa zic ca jumatate dintre noi nu ne-am fi apucat serios de informatica, munca voluntara pe care o faceti este una demna de admirat.
Felicitari pentru tot

In Q imi tin elementele pe care le-am folosit

Cod:

while (sf!=n)
    {
        MM=0x3f3f3f3f;
        int nod;
        for (int i=1;i<=sf;i++)
        {
            if (min[i]==0 || viz[cine[i]]==1)
            {
                min[i]=0x3f3f3f3f;
                for (int j=1;j<=n;j++)
                    if (!viz[j] && Q[i]!=j)
                    {
                        Dist=D(Q[i],j);
                        if (Dist<min[i])
                        {
                            min[i]=Dist;
                            cine[i]=j;
                        }
                    }
            }
            if (min[i]<MM)
            {
                MM=min[i];
                nod=cine[i];
            }
        }
        Rez+=MM;
        viz[nod]=1;
        Q[++sf]=nod;
}

cum fac sa fie mai eficient

Pai cum adik fac 'Prim', da de fiecare data trebuie sa imi recalculez distanta minima, eu aici pierd timp

Destul de Grea pentru o locala

Astept sa o scoata cineva de 100 sa imi zica si mie cum

ce memorie putina

mersi wef

Stie cineva unde pot gasi un articol bine explicat despre RMQ 2D?