Hello all!
I’ve been solving this question on Spoj GOODA - Good Travels. The problem statement is given a directed graph on N vertices and M edges with every vertex has a non-negative fun value F associated with it. You are given start vertex S and an end vertex E. You have to go from the S vertex to E vertex collecting fun value of intermediate vertices. Once you collect the fun value of a vertex then it fun value becomes zero, i.e you can’t collect the fun value from the single vertex more than once but you can visit any vertex any number of times. Constraints are given as
2 <= N <= 1e6,
1 <= M <= 1e6,
1 <= S,E <= N,
0 <= F <= 1e6, and
S != E
Now coming to my solution.
I first build the condensation graph of SCC’s of the above graph and stored the sum of fun values of each SCC component. Now the condensed graph will be acyclic. Now i just have to go from the SCC of vertex S to SCC of vertex E following the path that gives the maximum fun. I did it using dynamic programming but my solution kept on giving wrong answer on test #6 on Spoj.
Link to my solution is MY SOLUTION. Thank You very much for your time.