If you don’t want to use A*, you can also use dijkstra with a priority queue instead of computing the minimum, it works for the “large number of stages” test.
Hello,
I have the same problem as many, can someone who found the right solution provide the total distance he/she has found?
I ve found 13.551408331759312 for the solution taking in consideration the fact that stations have the same name.
When I check the solution of slava_spamec (which is also mie) I have 13.424056863059045
If you end up with the same road as slava_spamec, then my answer to his post is also valid to you.
To say it another way, the fact you have the same solution means you used a breadth-first search instead of Dijkstra’s algorithm. Though they’re pretty similar, Dijkstra’s needs a sorted queue because a path can be shorter even if it means going through more nodes. In a case where all distances between nodes are the same then a BFS is equivalent, but as soon as distances are different (as in this puzzle) a BFS doesn’t work anymore.
Passed all the tests in IDE.
Passed all the final tests except the last one : “Chemin impossible”
Cannot figure why.
Solved. I didn’t handled a case where a stop is a dead-end, ie a node you can reach but never leave . Don’t forget the graph is oriented !
I use Dijkstra, my queue IS sorted by distance and I get slava_spamec’s answer for the fifth test.
I already coded Dijkstra with the same code and it worked before.
I reread my distance function, of course I converted degrees in radians…
Then you can send me your code if you like, I could try to help you fix your issue.
Edit: To anyone interested as it was the issue here, and as already said in this topic: stop name is not unique whereas unique identifier is. This means you must not use the stop name as a key in your map/dictionary/whatever-it-is-called-in-your-language because 2 stops with the same name doesn’t have the same position nor the same links.
1 Like
Thank you.
How unlikely is that: My program passed all the tests in the IDE, but failed 5 out of 6 in the final valuation. I have absolutely no idea what the problem could be. Is there any way to get some feedback why the final tests failed?
PS: Now, it works. It seems that my old parser was too rigid for the input. Does anybody know whether the input does exactly match the specification from the description?
Take care to COMM -> COMM :o
Oh man, thank you so much! Was passing all of the IDE tests and then failed large # one in validation. Fixing now. Weird how it works for everything else.
i did A*! but not in C++
Tests in IDE pass but validation test “Large number of stages” is failed for me.
And I don’t have any hint whether it is performance or some liminal case.
If number of stations in IDE test and validation test differs significantly then it is not fair I think.
Read NewboO’s message: “stop name is not unique”.
really:
StopArea:HFNA,“Haute Foret”,47.23351996,-1.55542776,1,
and
StopArea:HFVE,“Haute Foret”,47.16828563,-1.46559936,1,
StopArea:BAIR,“Bel Air”,47.22556650,-1.55947121,1,
and
StopArea:BZIN,“Bel Air”,47.26678881,-1.48951130,1,
StopArea:HMVE,“8 Mai”,47.17268755,-1.47234134,1,
and
StopArea:MAI8,“8 Mai”,47.18909416,-1.55117093,1,
I’m in the same situation. I pass all validations in the actual question, but fail the large number and the 5 stops 2 routes.
Is there any way we can see what the input’s for those tests are?
Read NewboO’s message: “stop name is not unique”.
I don’t use the stop name for anything other than the final print. I use the ID (first param) for all references.
Maybe your algo is too slow.
I use Dijkstra’s, and I’d have hard time saying its too slow for those, but passes all the samples. Especially given one that it doesn’t pass seems to indicate its only 5 nodes big. I’m wondering if maybe there is some input variation, that I don’t parse correctly that is not represented in the samples…