15. SHPATH

[•cmiN]

Esec dupa esec ...
Am testat-o de-am inebunit si pe valori mari (mai mari decat in cerinta) si pe teste ciudate/lungi si totul e ok, apoi ii dau submit imi intra in 3.7s (sub 5 limita) de memorie nici nu mai vorbesc in schimb imi da WA: sursa la shpath.
Folosesc un simplu bfs cu actualizari pe un graf neorientat cu lista de adiacenta (in loc de Dijkstra).

L.E.:Cred ca stiu unde gresesc, dar acum iau sigsev (trebuie sa implementez coada aia calumea, uitam sa adaug nod in coada in momentul cand faceam o actualizare).

Edit2: Da ... cum credeam, idiotul din mine loveste din nou am reparat greseala (http://codepad.org/ahSZrldH) dar iau tle, era si cazul fiindca m-a mancat in cur sa nu bag Dijkstra.

Last edit: Folosind varianta cu limita de 25 de secunde (TSHPATH) nu pot scoate mai putin de 24 secunde (imi trebuie sub 20), varianta fiind asta. Am facut o versiune mult mai optima si mai "atenta", dar in practica se descurca ceva mai prost decat sursa de mai sus.

A iesit pana la urma s-o f*t: http://codepad.org/w4wD8YUl