257 Catun

[•VisuianMihai]

Da, am sortat fortaretele si am luat 100. Era gresita verificarea minimului cred. Mersi pt sfat

[•AlexandruValeanu]

Imi poate spune si mie cineva ce gresesc e iau 10p?

[•repp4radu]

Din cate mi se pare, gresesti in functia init.

Tu acolo iei vecinii fiecarei fortarete si le bagi distanta fata de cea mai apropiata fortareata, alaturi de indicele acestei fortarete.
Problema este ca tu vei face overwrite pe vectorul fort.

Sa presupunem ca ai fort = {1, 3, 4} cu indexare de la 1 si muchie de la 1 la 2 de cost 3 sa zicem.
Vei seta fort[2] = 1, iar astfel fort = {1, 1, 4}. Tu nu vei mai extinde fortareata 3.

Bafta! 

[•AlexandruValeanu]

Am gasit problemele...mersi de ajutor

[•swim406]

Iau 40 de puncte cu WA pe restul, si nu gasesc greseala nicidecum. Ma ajuta si pe mine cineva?

[•cont_teste]

@swim406
ai putea incepe prin a spune ce faci

[•drobert]

Prima data am facut cate un dijkstra cu heap de la fiecare fortareata si am luat 70 ( TLE ). Apoi am facut o singura data dijkstra introducand in heap fortaretele si iau 30 ( WA ). Imi puteti spune va rog unde gresesc la varianta cu un dijkstra ?

[•PlayLikeNeverB4]

Daca un catun este la distanta egala de doua fortarete, se va considera ca apartine fortaretei cu numarul de identificare minim

Nu cred ca iei in considerare asta.

[•drobert]

Am sortat fortaretele. Facand asta nu selecteaza automat fortareata cu numarul minim?

[•PlayLikeNeverB4]

Nu.

Cod:

4 3 2
1 3
1 2 1
2 4 1
3 4 2

[•drobert]

Am rezolvat-o. Multumesc mult!

[•vasica38]

Rezolvat 

[•serban_ioan97]

Imi poate da cineva testul 5? 

[•sicsic]

Putin ajutor??
http://www.infoarena.ro/job_detail/1562827
Folosesc Heap, si Dijkstra o singura data, plecand de la valori nule pentru fortarete.

[•PlayLikeNeverB4]

Scrie cod ingrijit daca vrei sa ti-l citeasca cineva.

[•sicsic]

Scrie cod ingrijit daca vrei sa ti-l citeasca cineva.

Am sters comentariile si am aranjat parantezele...mai e ceva?

[•flaviu_2001]

Am incercat si eu o implementare la pb asta, si am facut cate un dijkstra pentru fiecare catun, sa vad cea mai apropiata fortareata, dar imi iau un tle pe 5 teste. Any help?

http://www.infoarena.ro/job_detail/1736420

[•Bodo171]

Am incercat si eu o implementare la pb asta, si am facut cate un dijkstra pentru fiecare catun, sa vad cea mai apropiata fortareata, dar imi iau un tle pe 5 teste. Any help?

http://www.infoarena.ro/job_detail/1736420

Ceea ce faci e mai mult Bellman-Ford decat Dijkstra.Oricum,asta nu e neparat relevant.O ideea ar fi sa nu pornesti de la fiecare catun spre fortarete ci sa incepi cu fortaretele.Iti tii un vector de fortarete si unul de costuri.In vectorul de fortarete tii fortareata cea mai apropiata si in cel de distante distanta pana la ea.Initializezi distantele la toate fortaretele cu 0,iar fortareata cea mai apropiata de fiecare o setezi ca ea insasi(evident).Cand actualizezi distanta minima la un nod,actualizezi si fortareata cea mai apropiata care este evident,fortareata cea mai apropiata a nodului care il preceda pe nodul curent in drumul minim spre o fortareata.La final,afisezi vectorul de fortarete,iar pentru elementele care stii ca sunt fortarete,afisezi 0.Ideea e ca si la un Dijkstra/Bellman-Ford clasic,dar in loc sa incepi de la un nod,incepi de la mai multe,punandu-le pe toate in coada/heap initial,iar apoi actualizezi inca un detaliu pe langa distanta.
Sper ca am fost de ajutor.

[•flaviu_2001]

Gata, mersi fain, am facut sursa de 100p.

Cat despre confuzia mea dintre bell/dijkstra, cand am incercat prima oara sa invat dijkstra am gasit numai surse cu bell la problema de pe infoarena si am crezut ca aia e. Mai tarziu cand am invatat bell am observat ca sursele erau foarte similare intre ele si nu stiam care-i care. My bad..

[•robert_fanr]

Sal .
Testele de la problema asta sunt scrise prost pt java care aparent e ceva mai lent decat c++ ul .
Literalmente acelasi program ia numai 60 pct scris in java si 100 fara probleme scris in c++ .

[•AlexandruValeanu]

Nu testele sunt de vina. Limita de timp de la problema nu este adaptata pentru Java.

[•Constantin.]

putin ajutor va rog

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

nu inteleg de ce iau WA pe 5 teste. Fac Dijkstra punand toate fortaretele in heap la inceput, mentinand 2 arrayuri pt distante si fortarete. Am verificat si conditia pt catun minim.

[•Andrei-27]

In teste n <= 32000
 

[•Beard]

Eu am niste probleme cu testul 7. Primesc 90 puncet dar testul 7 nu vrea sa reuseasca.