102 Lanterna

[•repp4radu]

Cod:

672 580

[•Theory]

Thanks. Eu calculam drumul minim fara sa tin cont de K.

[•alexalghisi]

Aceeasi sursa aici ia 90p iar pe .campion 100  Ce are special aici testul 9 ? 

[•SebiSebi]

Am schimbat un test cu unul mai "provocator" si am reevaluat problema. (In caz ca va intrebati de ce unii au cu 10p mai putin decat inainte).  

Cred ca asta e motivul. 

[•alexalghisi]

Mda , un test atat de provocator incat majoritatea au 0/4 ms pe el   Si scuze , nu citisem acea postare 

[•SebiSebi]

Intotdeauna testele mici sunt cele provocatoare.

[•narcis_vs]

Imi arati si mie testul 9? 

[•hiticas_abel]

Personal cred ca ar trebui marit putin timpul de executie pe test. Sursa oficiala ia doar 90 de puncte cu TLE pe testul 7...

[•vasica38]

solved

[•stoianmihail]

Stiu ca suna cam dubios, dar merge cu un singur Bellman-Ford?(doar intreb ca poate, poate, cineva s-a mai gandit la ideea asta).

Eu m-am gandit ca se poate pleca cu parcurgerea din nodul N, calculand pentru fiecare nod necesarul minim de watti pe care trebuie sa-i folosim pentru a obtine distanta minima. Am implementat ceva care ia doar 10 puncte, dar sunt sigur ca aceasta idee trebuie sa mearga. 

Daca vede cineva comentariul acesta, il rog sa se gandeasca la ideea aceasta ca poate va reusi sa o implementeze perfect (eu ma voi stradui in continuare  ).

[•stoianmihail]

Da, merge! 

Am pornit Bellman-Ford-ul din nodul 1(nu din nodul N - cum am zis in comentariul trecut).
Deci, cine vrea sa implementeze aceasta idee, chiar ii recomand (e foarte asemanatoare cu cea de complexitate O(K * M * N)).

Cine vrea sa vada timpii -
    * ID: http://www.infoarena.ro/job_detail/1459472 (complexitate O(K * M * N))
    * ID: http://www.infoarena.ro/job_detail/1460000 (complexitate O(M * N))

Bafta!

[•Corneliu10]

Poate sa-mi dea cineva testul 9?

[•blackodd]

Ce pana corbului are asa special testul 9?