Guys,
Can somebody give me a hint to avoid Memory Limit (I use C#)?
I've tried a lot of algorithms:
1. Composing full graph by using digits tree for all numbers. Processing graph by using Dijkstra and PriorityQueue (SortedArray<ShortestDistance, Queue<VertexIndex>>).
2. Creating tree of digits for all numbers. Processing graph "on the fly": obtaining all neighbor vertexes for current vertex (from previously created tree). The Dijkstra and the same PriorityQueue were used.
3. Using Dictionary<PhoneNumber, VertexIndex> for storing all numbers and vertexes. Processing graph "on the fly": obtaining all possible neighbors (135) and filter them by real vertexes from dictionary. The same PriorityQueue was used.
4. The same as 3, but instead of PriorityQueue, I've used Heap<ShortestDistance, VertexIndex>. After distance to some vertex was updated, I remove this vertex from Heap (if it exists there) and add it again, but with new key (distance).
I even replaced usage of all pointers to objects by UShort indexes, and now I'm in stuck.
I've started work on this task because accidentally send solution of other task here, but now I already hate test #8 :) Any ideas?
