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.

Try to use numbers instead of strings

How to cope with the strings? I put all strings to a map, then for each string I construct all possible neighbours and then I check if they are in a map. So I have to deal with 50000 * 135 * 16 = 108 000 000 operations. It is too much. I can use a hash table. However, is there any simpler solution than using the hash table?

You can use strings (because it's so conveniently), but you have to forget about std::map. Use unordered_map<string> (or your hash table) instead of it. I had TLE on test 11 with std::map, but when I changed map to unordered_map, I got AC with not bad time. I think it's easier than use numbers instead of strings.