Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=516 Official Solution: http://www.usaco.org/current/data/sol_grass_gold.html

I was able to reduce the problem to solving it on a weighted DAG after compressing the graph into strongly connected components. However, I am not able to handle the caveat of being able to traverse a reversed edge at most once.

Is there a way to solve this final step of the problem without dynamic programming? If not, can someone explain what exactly is going on in the "solve" function and calls to it?

Please help, and thanks in advance!