I'm having a hard time formulating an algorithm in solving a Dynamic Programming Problem that involves looking for the cheapest path of a given digraph.
the twist though, is that you have to look for the cheapest path from point 1 to k, but when you have a path from point 1 to k, the second most expensive path will be free.
For example, if a path from 1 to 10 is 1>4>6>10 with arc costs 5,6,3,4 respectively, arc 1 will have 0 cost. then, its total cost will be 6+3+4 = 13. I'm supposed to minimize this cost.
Help me guys...