![:(](./images/smilies/icon_frown.gif)
As we are dealing with undirected graph, can i and j change place ??Cuv = Sum (PreCostij -CurCostij) where CurCostij is the shortest cost path from i to j if the road between (u, v) exists. And PreCostij is the shortest cost route before constructing the road between u and v.
e.g. Will both PreCost(1,2) and PreCost(2,1) both be considered while calculating the sum ???
And is there any tricky input for this problem?? Please somebody help me with some sample I/O s.
My algo works as follows:
- Floyd-Warshall to get the shortest path
- Select an edge/road for construction (if it was not initially given)
- Update the total cost for the graph, for adding the current road using an O(n^2) loop
- Show the best road (IF REQUIRED)