http://www.spoj.com/problems/FISHER/
This task is possible to solve with both dynamic and recursive approach. Here I will present you the recursive one. We can have an obvious DFS(you can find more info about DFS here approach, start with the 1st and take every single path, I am not sure whether the simple DG We can use some optimizations to reduce the time. Our DFS should have 3 parameters: N,M,T. N shows the node we are currently in , T shows the time it took us to reach the current node, and M shows the money we paid so far. Here are some optimizations you should do. We also have 2 parameters ansT and ansM which show the answer ansT stands for time and ansM stands for money.
1. Marking the node we already visited, (of course don't forget to unmark it after the recursive call).
2. If the current money we have already paid is bigger then the answer we have got previously then here is no need in continuing our recursion because we are not going to get a better answer.
3. If the time which we have spent is greater then the given maximum time we need to break our recursion immediately.
Also check the source code for a better understanding.
This task is possible to solve with both dynamic and recursive approach. Here I will present you the recursive one. We can have an obvious DFS(you can find more info about DFS here approach, start with the 1st and take every single path, I am not sure whether the simple DG We can use some optimizations to reduce the time. Our DFS should have 3 parameters: N,M,T. N shows the node we are currently in , T shows the time it took us to reach the current node, and M shows the money we paid so far. Here are some optimizations you should do. We also have 2 parameters ansT and ansM which show the answer ansT stands for time and ansM stands for money.
1. Marking the node we already visited, (of course don't forget to unmark it after the recursive call).
2. If the current money we have already paid is bigger then the answer we have got previously then here is no need in continuing our recursion because we are not going to get a better answer.
3. If the time which we have spent is greater then the given maximum time we need to break our recursion immediately.
Also check the source code for a better understanding.
Why can't we use Floyd Warshall Algo here ?
ReplyDelete