I am working on (http://www.spoj.com/problems/SAMER08A/) problem.
Now it is clearly mentioned in the problem that a route in the second shortest path cannot coincide with the route already present in the shortest path.
Here is the exact words from the problem statement:
“He defines the almost shortest path as the shortest path that goes from a starting point to a destination point such that no route between two consecutive points belongs to any shortest path from the starting point to the destination.”
If I consider the following test case
9 11
0 3
0 1 10
0 7 80
0 4 22
1 4 11
1 2 10
2 3 10
4 5 5
5 6 2
6 3 2
7 8 100
8 3 20
0 0
The shortest path is of length 30(0->1->2->3 ) and the second shortest path is of length 31(0->4->5->6->3)
However when i checked my answer with some of the accepted solution the answer was 200.
I guess the breakdown for the answer to be 200 was the following:
first shortest path is 0->1->2->3 of len 30
second shortest is 0->1->4->5->6->3 of len 30
and then comes the remaining i.e 0->7->8->3 of length 200.
Isn’t the second shortest path computed incorrectly in this case.
Here is my solution if it helps:
https://ideone.com/LSaQve