I implemented the first idea came to my mind: for each connected vertices v1,v2 removing edge v1-v2 and finding shortest paths from v1 to v2 with Dijkstra. As for my estimations it should be O(edges^2) or O(vertices^4) for very connected graphs.

It was reported in other threads of this discussion that this solution should fit time limits, but mine does not pass test #3 (time limit exceed).

I am curious if solutions like mine now can be accepted. Did anyone have success with that approach after rejudgement in Sep 2013? Or now only O(v^3) solutions can pass all tests?

Thanks