I use Dijkstra too, and it works.
My algo failed when I did not use the right key.
Like explained in posts above, be sure to use radians for your distance computations and not degrees.
to convert use the following formula when fetching latitudes and longitudes
x (radians) = x (degrees) * pi / 180
I had the same problem (all validation samples ok but missing one in the real tests so 84%), and adding the conversion finally got me 100 % 
1 Like
Passed with Dijkstra in C++ using maps, they are logarithmic for searching with the string identifier keys but when I search for the next shortest path at every iteration of dijkstra I have to linearly go through a map. Probably not optimal.
Thanks a lot NewboO !! I had the same problem and it was indeed the conversion of latitude and longitude into radians that I forgot to do. It is really weird that we managed to pass all the IDE tests cases with degrees instead of radians !
Another mistake connected to these unfortunate form of coordinates is order in what you read latitude and longitude, because even if you take them in wrong order you will still pass all tests in IDE and fail only one (Large number of stages) on submit.
1 Like
I also had problems with āLarger number of stagesā during validation. Iāve made a faster short path finder, and solved the problem. But I still donāt know if the problem was the time of execution, because the older program can run 3 times in the IDE test (calling 3 times the short path routine) without problem with time. So, the validation test is much longer or has a case that my old program cannot solve.
I think it would be a good idea, if validation tell us the cause of the problem (time of execution or wrong answer).
Thank you very much! Same thing here. Itās a nasty trap.
Degrees to radiansā¦ thanks, you save my time ^^
1 Like
LOL TY Bro I was using a super fast implementation of Dijkstra with a Min-Heap and still failing the large test case.
after converting it to radians I passed 
Same for me! Thanks a lot for this tip! You saved me from madness
In the question it lists the information about each stop, with some items being listed as ānot usedā. There is one item however (āThe type of stopā) which is not explained, and does not appear to be used, but is not labelled as such. Anyone know what it is meant to be for? It doesnāt seem necessaryā¦
1 Like
Ha la la la la !!! Iām so dumb !!! :))
Every week for several months, iāve found some time to read my code again and again because of this 83% submissionā¦
Sure my Dijkstra was good ! Sure my degrees to radians conversion was good ! Everything was good in fact but always 100% in IDE and 83% in validationā¦
And today, i found it. Very funnyā¦ I was reading x = latitude and y = longitudeā¦ So bad because x is longitude and y is latitudeā¦ Reading y before x does the job !!! 100% Yeah ! Too gladā¦
2 Likes
Hi guys, Iāve read all your posts and taken everything in consideration. I convert latitude and longitude to radians when I fetch them by multiplying by the (pi / 180.0) factor. I use them correctly in the formula and I never use a name as a key for any of my maps. I get 100% on tests and fail on submitā¦ any more ideas ?
Thanks a lot
1 Like
I finally found my problemā¦thanks to those who tried to help ! (problem was I was only initializing the distances of the stops which are at the beginning of a routeā¦)
Hi guys,
Iām stuck at 83% in validation but my problem is with the 5th validator (5 stops, 2 roads).
Iāve converted my degrees to radians and Iām sure about my lons and lats so I have no idea where my issue could beā¦
If any of you have a tip or a guess about my problem, please do not hesitate to answer me
youāre the real mvp !
Well thatās funny because when we invert longitude and latitude, we pass all the tests in IDE. (but one failed during the validation)
Please, make an IDE test for that or something 
1 Like
Same problem here.
I use Dijkstra (A* with 0 heuristic) implemented in C++ and it passes all the tests in IDE and fails the āLarge number of stagesā in the verification phase. I have no idea why it does and canāt fix it for days 
I also tried using float and double as well for distnance calculation.
So if you succeeded to solve the problem please let me know.
Solved: Convert degrees to radians
2 Likes
suddenly, i decided to solve this in pure C, just to see other peopleās solutions if there is something funny
i had this solved in pascal so i was pretty confident that iāll do it in no time
debug was terrifying, took me three days
and what i see as a result? only one participant except me also solved this in C
frustrated
1 Like