You are not logged in. Please login at to post your questions!


GOODA SPOJ Problem, Need Help!

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.

asked 23 Oct '18, 16:27

meet2mky's gravatar image

accept rate: 26%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 23 Oct '18, 16:27

question was seen: 57 times

last updated: 23 Oct '18, 16:27