|
Titlul: 15. SHPATH Scris de: Cosmin Poieana din Iunie 11, 2011, 21:34:42 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 (https://ideone.com/EaTFg) la shpath (https://www.spoj.pl/problems/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 (http://pastebin.com/9u9epnh3). Am facut o versiune (https://ideone.com/l4glD) 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 |