223 Srevni

[ditzone]

Aici puteţi discuta despre problema Srevni.

[•pauldb]

In exemplu am arcul [1,3], iar costul in nodul 1 e 1, iar in nodul 3 e 4, asta nu inseamna produsul va fi adus in nodul 3 din nodul 1 cu costul 1?

[•pauldb]

Interesant...cred ca e gresit enuntul...drumurile sunt de la Y la X. Am luat 100 dupa ce am inversat muchiile. 

[•wefgef]

e bun enuntu.

masina de comanda care trebuie sa alimenteze orasul i pleaca din orasul i spre orasul din care trebuie sa aduca alimentele. In momentul cand ajunge la destinatie este incarcata si teleportata in orasul i.

asta inseamna ca un oras X poate sa se alimenteze dintr-un oras Y daca exista o modalitate de a ajuge din X in Y.

in exmplu nu poti ajunge din 3 in 1.

[•pauldb]

Da...sorry...my bad...e bun enuntul. 
Next time o sa incerc sa citesc mai atent enuntul.  :sad2:

[•informatician28]

Eu nu prea am inteles exact ce cere pb. Eu am facut un DFs pt fiecare nod si pt fiecare nod in care se poate ajunge din nodul respectiv am comparat daca valoarea asociata nodului "radacina" (cel pt care am facut parcurgerea initial) are un cost mai mare decat nodul la care am ajuns. Daca da, la minim ii atribui aceasta valoare.
In acest fel pt fiecare nod fac DFs si calculez minimul asta. Totusi, iau 0 pct. Ce gresesc? 

[•informatician28]

Am rezolvat-o

[•superman_01]

Buna ziua,
Ma chinui la problema asta de ceva timp si nu am reusit sa iau decat 95 de pct ( TLE pe ultimul teste ) . Fac un DFS din fiecare nod . Nu imi dau seama cum sa scap de TLE , am incercat si cu parsare si tot aia. Ce ar trebui sa fac sa scap de TLE ?
Multumesc anticipat!

[•CosminRusu]

Iei TLE pentru ca solutia ta nu e optima. Nu e nevoie sa faci un DFS din nodul i in toate nodurile. Gandeste-te cum te poate ajuta sortarea vectorului de costuri.
Bafta!

[•superman_01]

mersi ...mi -a iesit 

[•Sapientia]

Iau 85 de puncte cu dfs pentru fiecare nod...nu-mi dau seama cum sa-l optimizez cu o sortare...un indiciu?

[•visanr]

Poti, spre exemplu, sa faci un graf, unde muchia X - Y din input e Y - X in graful tau (ti se spune ca X poate primi alimente de la Y daca exista drum de la X la Y, dar in continuare vom pleca de la nodul care distribuie spre nodurile care primesc).
Parcurgi nodurile crescator dupa cost, iar daca esti la nodul i si i e nevizitat, inseamna ca nu poate primi alimente de la niciun nod cu cost mai mic si Ans[ i ] = cost_initial[ i ]. Faci un dfs din i si marchezi nodurile nevizitate cu costul initial al lui i, nodurile parcurse in dfs neavand asociat un cost mai mic decat cost_initial[ i ]

[•alexandruchiriac]

A primit cineva Killed by signal 11 ( SIGSEGV ) ?
Nu stiu cum sa scap de aceasta eroare.
Nu accesez memorie nealocata, sa fie din vina dfs-ului ? Sa se auto apeleze de prea multe ori ?

[•Bodo171]

DFS-ul tau cicleaza la infinit si umple memoria pe stiva,de acolo KBS 11(fii atent cum marchezi nodurile vizitate!).