Floyd warshall algorithm would've been fine if n wasn't 1e5. Do you have link to the question? or is it yours?

Also tell us about number of edges and time limit.

I think this works ..

1. Run Dijkstra twice, one from the source (on the original graph) and one from the destination (on the reversed graph). Store shortest distances from each node to the source and the destination.
   
2. Now for every edge say E(x,y) connecting nodes x and y. Making it bidirectional is just merging x and y. So now the shortest path is determined by the minimum among actual min distance b/w source and destination and ( min distance among source to x, source to y + min distance among x to destination, y to destination ).
3. The optimal route can be one of these 5 cases based on 5 possible cases for the above equation:
   
   • Actual optimal path from source to destination
     
   • source -> x + x -> destination
     
   • source -> x + y -> destination
     
   • source -> y + x -> destination
     
   • source -> y + y -> destination
     

[Deleted]