Regarding A-star, it doesn't generally come up in this kind of contest. When you are doing a TopCoder/ICPC/Project Euler problem and you need to find shortest paths, you need exact solutions because you want your result to match the judges' result. In a programming contest in which the programs compete against each other, instead of passing or failing, A-star would be much more important.