this is a O(n^3) algo for this problem:
- for each node such v, first you use dijekstra which have a "v" as a root, then you   clacute the:
            k= E.wei + dis[E.e1]+ dis[E.e2].
  where E is a edge that not exist in a tree of dijekstra algo, and E is
  a (e1, e2). and at the end you must print the minimum of all the k.

sorry for my poor english.

Edited by author 12.11.2010 11:12

Edited by author 12.11.2010 11:13

Well, I solved this problem in O(n^4) fixing a deleted edge and then running dijkstra from one it's vertex to the other, but I want to get better. :-)

However I failed to understand your post at all. Could you explain it somehow?

Edited by author 13.01.2012 05:11

I read all the posts, collected input test cases posted by people, and passed all of them successfully, but, unfortunately, still i am getting WA#test case 1. Tried everything. But found no clue why my solution is getting WA. Please help me out.

Very good idea, thanks for sharing!