009 Algoritmul lui Dijkstra

[•soriyn]

Merge si pe grafuri neorientate daca la citire adaug ?

Cod:

add(y,x,z);

L.E. : si se poate sa opresc algoritmul cand am ajuns la un anumit nod final ? Daca da, cum ?

[•blasterz]

Merge pe grafuri neorientate.
Cred ca te poti opri la un anumit nod final atunci cand ai relaxat toate muchiile catre acel nod.
Totusi nu cred ca vei imbunatati prea mult algoritmul.

[•vlad.doru]

Are cineva vreo idee ce as putea sa fac sa imi intre in timp pe ultimu test? Deja cred ca o iau cu capu 

[•vlad.doru]

Am trimis si sursa oficiala si nici ea nu ia 100 de puncte. Cred ca ar trebui sa modifice cineva timpul maxim de executie.

[•sunt_emo]

Nici sursa mea nu reuseste sa se incadreze in timp. De fapt ma mira faptul ca iau alte surse de 100 de puncte (destul de recente), le retrimit si acum nu iau decat 80-90p. Am implementat Dijkstra cu heap, am optimizat tot ce se putea (in limita geniului meu )) ) si degeaba

[•sunt_emo]

Apropo, imi explica cineva cum sursa http://infoarena.ro/job_detail/629253?action=view-source ia suta? Cred ca is atat de bune testele ...

[•soriyn]

Se mai poate lua 100 fara parsare ? N-ar strica marita putin limita de timp..

[•psycho21r]

Se poate șterge ultima mea sursă trimisă pentru problema asta? Am încurcat problemele. 

[•mening12001]

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


as fi deosebit de recunoscator celui ce isi va dedica o mica parte din timpul sau pentru a'mi explica ce anume este gresit la aceasta sursa

[•PlayLikeNeverB4]

Nimeni nu isi va dedica timp sa iti citeasca sursa in halul in care este scrisa. Ar fi bine sa urmezi sfaturile de aici.

[•mihaipopa12]

In cazul in care afisezi 0, in loc de '0 ' trebuie sa pui "0 ".

[•mening12001]

iti mulrumesc..
si totusi, am luat 50 p, iesindu'mi din timp

[•pbobitza]

Am incercat sa rezolv problema cu algoritmul lui Bellman-Ford (sursa ia 100 pct ) insa nu stiu de ce nu iau mai mult de 10pct aici ,pe restul testelor e incorect...
Daca aveti putin timp sa dati "o geana" pe cod as fi recunoscator

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

[•gabitzish1]

Testele problemei sunt publice. Ai putea sa downloadezi testele mici si sa vezi ce rezultate scoate programul tau.

[•laurion]

Am incercat sa rezolv problema cu algoritmul lui Bellman-Ford (sursa ia 100 pct ) insa nu stiu de ce nu iau mai mult de 10pct aici ,pe restul testelor e incorect...
Daca aveti putin timp sa dati "o geana" pe cod as fi recunoscator

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

Aruncand un ochi rapid pe sursa ta, trebuie sa verifici/adaugi in coada vecinu' doar daca are distanta mai mica, pe cand tu ai if-ul ala in afara primului, baga-l inauntru.

[•pbobitza]

if (d[a[nod].n]>d[nod]+a[nod].c)
            {
            d[a[nod].n]=d[nod]+a[nod].c ;
          if (inq[a[nod].n]==false)
             {q.push(a[nod].n);inq[a[nod].n]=true;}
            
           }


Se pare ca erau acolo parantezele :)Multumesc oricum!

L.E. Imi e rusine sa spun care era problema! ) out>>"0" in loc de out>>"0 " ...
Multumesc pentru ajutor!

[•laurion]

mda, pai aici trebuie sa te inveti si tu sa codezi frumos... din indentare parea ca if-urile alea 2 sunt separate

[•visanr]

Imi puteti spune si mie va rog ce mai pot optimiza la sursa asta http://infoarena.ro/job_detail/735388?action=view-source ? Am facut cu priority queue, cu stream-uri si tot iau TLE pe 3 teste, al 4-lea test gresit are incorect.


Multumesc!


LE: nu am mai dat edit atunci, am facut-o de 100.

[•danalex97]

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

Aveti idee ce poate fi gresit ? Dijkstra cu heap-uri. Tin sa mentionez ca , cu acelasi cod putin modficiat la complexitate O(M lg M) iau 90 cu un TLE.

Multumesc anticipat !  :ok

LE: Solved. 

[•dutzul]

ma poate ajuta si pe mn cineva numi dau seama ce greseste programu. am facut cu bellman ford.
iau KBS si incorect http://infoarena.ro/job_detail/768454?action=view-source

[•visanr]

In primul rand, la BellmanFord adaugi in coada un nod nou daca nu e deja in coada, pt asta tii inca un vector. Alta observatie, in loc de deque poti folosi direct queue. Mi se pare ca trebuie sa folosesti .size() in loc de .capacity() la forul de la BellmanFord.

[•dutzul]

nu nu asta era problema nu trebe nici un vector. problema venea de la ceai zis tu cu size() in loc de capacity() .. nuntaleg care e diferenta:X
thnx

[•visanr]

Aia cu coada era o varianta mai simpla. Uite aici ai diferenta intre capacity si size: http://www.cplusplus.com/reference/stl/vector/capacity/ http://www.cplusplus.com/reference/stl/vector/size/

[•Alexu]

Stie cumva,cineva daca se poate face si prin backtracking? Multumesc anticipat !

[•PlayLikeNeverB4]

Se poate. Dar timpul de executie va fi extrem de mare.