OJ Board

The problem states that given a set of numbers, find the minimum number of cut/paste operations required to get the numbers into a sorted sequence. The cut operation can involve one or more consecutive numbers.

For eg.
given the sequence
1)
...2 4 1 5 3 6
we cut 4 and paste it before 5 to get ...

i had completely forgotten about multiple shortest paths. After I realized the same, I modified my code into a djikstra's single source shortest path program with every node having a predecessor list. This got accepted by the judge.

On a side note, is there any way to recover all shortest paths ...

This problem looked easy and I attempted the following to solve it,

1) Found the shortest path of the boss home to office using all pair shortest path and then removed the shortest route (made the distance to these vertices as infinity) from the graph.
2) In the new map, tried to find the shortest ...