do not use many nodes if there is no path between them! PLEASE...
It is necessary to compare the speeds of algorithms for finding an existing path, rather than the speeds of algorithms for finding the fact that there is no path.
P.S. And the computing capabilities of the russian Anka are simply amazing! :-)

you need to check, what element exist in your map

use unordered_map instead of map

I used Dijkstra+heap optimized but still got TLE on #11..
Is there some better algorithm?
help..
my email:caoyuan@mail.ustc.edu.cn
thx.

47 times i had submitted a code with a small bug in heap... I'm sad...

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?

50000
1 1 1 1 1 1 1 1 1 1
0000000000
0000000001
0000000002
0000000003
0000000004
.
.
.
0000049994
0000049995
0000049996
0000049997
0000049998
0000049999

AC

Edited by author 09.11.2010 02:11

Please Help me, i get WA #11 many times.
My solution in Java
1) For each "phone number" get list neighbours
2) use PriorityQueue to find shortest path
3) print path
For calculations with "phone number" use Long
for init max_time use 10^12
I can send my solution on mail.
Sorry for my english.

Is it possible to solve it in Java without any special tricks?
I got MLE #16 any time when I submitted it in Java. Of course, the same C++ code gets AC and uses 35 MB.

I think that it is not good when equal solutions get different verdicts. Am I right? Admins, maybe you should increase memory limit?

Edited by author 01.11.2010 10:11