180 Drumuri minime

[•MarcvsHdr]

Pai in primul rand, testul lui Marius nu e bun  . (ala, primul... cu muchiile de cost 1). De ce? Pentru ca orice drum intre 1 si X e minim (orice produs e 1, sau altfel spus, orice suma de logaritmi e 0).
De altfel spune si in enunt, ca dimensiunile sunt intre 2 si 10^9.

Raspunsul ar fi
5 6 4 4                        - daca drumurile sunt elementare
infinit infinit infinit infinit - daca drumurile nu sunt elementare

Nu scrie nicaieri daca drumurile sunt sau nu elementare, pentru ca reiese din conditia de drum minim (din nou, daca costul fiecarei muchii >1)

Cat despre precizie... sa ma dau cu capul de pereti, nu alta   

[•Mishu91]

Testele nu cred că sunt foarte puternice, pentru că iau 100 cu Belman-Ford, care teoretic nu ar trebui să ia maxim, pentru că nu generează întotdeauna soluția corectă.

[•ciprianf]

@ Mishu91
Ce vrei sa spui prin faptul ca Bellman ford nu genereaza intotdeauna solutia corecta?

[•Mishu91]

Uite pe exemplul următor (lungimile sunt deja logaritmate, să zicem).

Cod:

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

Tu când faci Bellman-Ford ai în coadă 1, mergi la 3 și 2. Apoi din 3 mergi în 4 cu costu 4 (deci un drum de cost 4). Din 2 mergi în 4 și în 3, deci o să ai 2 drumuri de cost 4 în 4, dar pe 3 îl updatezi, dar nu îl mai bagi în coadă (cel puțin eu așa am făcut), prin urmare pierd un drum de lungime 4 între 1 și 5(1-2-3-5)

[•ciprianf]

Pai atunci baga-l iar in coada dar ai grija ca sa nu aduni de mai multe ori acelasi drum.
Dupa ce relaxezi vecinii unui nod, NR[nod] = 0 (avand grija sa pastrezi in alt vector valoare NR[nod])

[•Mishu91]

Ai dreptate, pare a merge așa, dar testele tot slabe sunt.