994 Retea

[•Prostu]

Aici puteţi discuta despre problema Retea.

[•Andreid91]

Care e jmecheria de reduce timpul de executie la 0.5-0.6 ?   

Am incercat sa evit operatiile cu nr reale si am inmultit cu 2^10...pare sa fie mai ineficient..

[•stocarul]

Păi din ce am citit în soluția oficială, trebuie Dijkstra în loc de Bellman-Ford. Desigur, am simțit asta și pe pielea mea ......
Iar dacă vrei să eviți folosirea numerelor reale, trebuie să folosești long long.

[•Andreid91]

Pai dijkstra am folosit si eu...am retinut  o matrice dist[n][k] si inca una poz[n][k] in care retin pozitia nodului (n,k) in heap.  ( heapul e un record in care retin n si k. am incercat sal retin pe biti ,adik h[p]=(i<<4) + j, dar timpul de executie a crescut )

Si ziceam ca e mult mai ineficient sa retin matricea dist pe tip long long si sa evit operatiile cu nr reale...

Probabil trebuie sa fie mici detalii de implementare 

[•stocarul]

Încearcă ca tot în heap să reții și costul, pentru ca atunci când faci comparări, să nu accesezi matricea (ci tot în heap). Eu așa am făcut trecerea de la 80 la 100 de puncte  

[•vendetta]

Salut!
Am complexitatea(M*K^2*logN) şi iau 40 de puncte cu tle. Iniţial mi s-a părut mult pentru 0.3 aşa că am încercat să optimizez soluţia dar nu am reuşit. Am citit soluţia şi spre surprinderea mea şi complexitatea oficială e la fel. Din ce cauză iau tle ? (Dijkstra l-am implementat cu priority_queue.) O fi de la evaluator sau de la mine ?!

[•poptibi]

Se pot lua 100 de puncte cu Bellman-Ford / Dijkstra cu priority_queue? Cu Bellman-Ford am luat 50 cu TLE, iar cu Dijkstra 40 cu TLE, dar nu stiu daca e limita de timp prea mica sau mai trebuie sa optimizez. 

[•Magnvs]

da, eu am luat 100 cu dijkstra cu priority_queue.

zisesem mai devreme sa pui long long in loc de double, aparent merge mai prost, deci lasa double.

alta faza ar fi ca atunci cand ajungi la destinatie sa opresti dijkstra-ul si sa expandezi un nod doar o singura data.

[•poptibi]

da, eu am luat 100 cu dijkstra cu priority_queue.

zisesem mai devreme sa pui long long in loc de double, aparent merge mai prost, deci lasa double.

alta faza ar fi ca atunci cand ajungi la destinatie sa opresti dijkstra-ul.

Am reusit sa iau 100, mersi mult Magnvs!  

[•AndreiGrigoras]

Costurile pe muchii sunt numere naturale ?