009 Algoritmul lui Dijkstra

[•wefgef]

Se poate: http://infoarena.ro/job_detail/154087?action=view-source

[•toni2007]

e BF cu heapuri?

[•bogdan2412]

vectorii cu "heap" nu sunt folositi si probabil au ramas de la sursa in care a facut dijkstra

[•toni2007]

am implementat cu Bellman-Ford cu coada dar iau doar 30 (ok pe 1 2 si 8 , 5 wa si 2 TLE <astea se rezolva cu parsarea citirii>) si nu-mi dau seama unde crapa... ma poate ajuta cineva?

http://infoarena.ro/job_detail/183901?action=view-source

[•amadaeus]

In principiu, bagi un nod in coada numai daca nu este deja acolo. Vad ca tu bagi un nod in coada la fiecare relaxare.
Nu stiu daca WA e de la asta, dar.. pune si conditia asta prin sursa

[•toni2007]

Nup nu e de la asta. cu chestia ta iau doar 10 puncte pe testul 8. Eu bag un nod in coada de mai multe ori doar daca costul obtinut pana atunci este mai mic decat costul obtinut mai devreme, si atunci trebuie sa reactualizez si toti vecinii lui.

[•wefgef]

Pai nu trebuie sa bagi un nod in coada decat daca nu este deja acolo.

[•amadaeus]

M-am uitat inca o data peste sursa ta si am vazut ca tu tii o coada de structuri cu nodul si distanta pana la el. Am impresia ca aici complici lucrurile; eu propun urmatoarea varianta: tii un vector dist[ x ] in care retii distanta minima (pana in prezent) pana la nodul x, iar in coada bagi numai indicii nodurilor, nu si distantele. Din nou, bagi un nod in coada numai daca nu este deja acolo.

Asadar, transformarile intr-un pseudo-C ar arata cam asa:

Cod:

coada.push( 1 );
incoada[1] = 1;

while( !coada.empty() ) {
	u = coada.pop(), incoada[u] = 0;
	for( v vecin al lui u )
		if( dist[v] > dist[u] + cost(u,v) ) {
			dist[v] = dist[u] + cost(u,v);
			if( incoada[v] == 0 )
				incoada[v] = 1, coada.push(v);
		}
}

[•wefgef]

Am scris acum o sursa cu bellman-ford. Poti sa te uiti peste ea daca vrei.

[•amadaeus]

  Sunt mai rapide streamurile decat ma asteptam... Eu am luat mai demult, pe aceeasi idee, 90 cu citire standard. La ONI se va folosi tot g++ 4.2?

LE: Nop, citat de pe site-ul oficial:

5. Linux    g++ 3.2.2    compilator pentru limbajul C++

[•toni2007]

@wefgef
nu prea stiu c++ si chestii cu push si iteratori

@amadaeus

dap. asta pt ca se foloseste evalul . campion care merge doar pe gcc vers 3.

[•wefgef]

Pai de ce nu inveti? Crezi ca e asa mare filozofie?

Exact, ce anume nu intelegi din sursa mea?

[•toni2007]

cum e cu iteratorii

[•amadaeus]

Iteratorii sunt un fel de pointeri, cu care poti parcurge un container (de exemplu un vector).
Iti recomand cartea "STL Tutorial and Reference Guide", de Musser, Derge si Saini - dupa bucata introductiva iti vei forma o parere destul de clara asupra STL-ului, iar acesta va fi un pas mare inainte

Daca nu gasesti in alta parte, am uploadat-o aici.

[•wefgef]

  amadaeus.

Ceea ce fac eu acolo cu iteratorul este parcurgerea listei de vecini. As fi putut sa fac asa:

Cod:

for (int i = 0; i < int(G[nod].size()); ++i)

iar in loc de it->first as fi avut G[nod][ i ].first si in loc de it->second as fi avut G[nod][ i ].second.

[•toni2007]

Am reusit in sfarsit sa iau 100 dar cu citire cu streamuri ( cu citire in c imi crapa)... si testele par ciudate: imi crapa mozilla cand intru in ele

LE: gata... am scos 100 si cu citire in c (si 428 de ms pe cel mai mare test) cu bellman ford cu coada

http://infoarena.ro/job_detail/185953

si se pare ca sunt singurul cu c care a luat 100


deci se poate si in c

[editat de moderator: nu posta de mai multe ori consecutiv, foloseste edit]

[•amadaeus]

Daca parsezi citirea, se poate in C si cu Dijkstra cu heapuri (http://infoarena.ro/job_detail/186013)

[•toni2007]

dap. si e chiar mai rapid cu heapuri. Dar eram primul care a luat 100 in c

http://infoarena.ro/monitor?task=dijkstra&&compiler=c&&score_begin=100

aici apar toti cu 100 in c pe dijkstra

[•bogdan2412]

oricum probabil exista destule surse trimise cu cpp care ar compila in c si ar lua 100 

[•Cosmin]

@Airinei

Auzi, ma uitam la sursa ta ce e linkata din problema si vad ca folosesti set cand puteai folosi priority queue fara nici o problema. Nu folosesti nimic din avantajele setului aici ...

Si inca o chestie, cred ca faci chestii redundante pentru ca nu faci lazy deletion. Inainte de a folosi o valoare din heap poti sa testezi daca valoarea ce o folosesti in relaxari. Trebuie sa testezi if (val > d[ x ]) continue;

[•toni2007]

am trimis de mai multe ori aceeasi sursa, a doua oara cu niste comentarii in ea,

http://infoarena.ro/job_detail/193067
http://infoarena.ro/job_detail/193068

si obtin timpi foarte diferiti... gen 500 si 472. stiam ca de obicei timpul poate varia cu cel mult 8 ms dar poate chiar asa de mult? Adica 30 de ms? Poate fi de la alocarea dinamica a memoriei?

Need help...

[•stef2n]

E nesemnificativa diferenta La problemele cu limite mari de timp (3-5 secunde) mi s-a intamplat sa am diferente pe aceeasi sursa de 50-100 ms.

[•mihai0110]

am incercat cu bf cu coada si vad ca primesc tle desi sunt sub 0.5 sec 

 10   472ms   4792kb   Time limit exceeded.   0

sau

 10   488ms   4788kb   Time limit exceeded.   0

in timp ce pe sursa lui wefgef

 10   488ms   4564kb   OK   10
 

[•sima_cotizo]

Evaluatorul are o mica eroare in masurarea timpilor de executie afisati, dar fii sigur ca algoritmul tau este oprit atunci cand depaseste timpul.

[•c_e_manu]

poate cineva sa arunce o privire aici si sa-mi spuna unde e greseala... am incercat in nu mai stiu cate feluri si tot nu reusesc sa gasesc ce nu e in regula... mersi!

http://infoarena.ro/job_detail/267069

LE: am marit coada si intra pe 9 teste... pe al 10-lea iau TLE... o sa implementez coada dinamic si atunci sper sa intre... are totusi cineva vreun pont cum sa nu bag de mai multe ori acelasi nod in coada, in afara de STL?