3
$\begingroup$

Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output the path taken, as well as total coins taken. You may only travel in the direction of the arrows. We are allowed to take the same path twice. The solution for the situation in the figure below is the path 1 - 4 - 3 - 2 - 1 - 5 - 7 - 9 - 10 - 8 - 12, with a total of 7 coins. I think this should be possible in linear time. My idea so far is to start at the last node and go back, saving the "best attainable score" for each node. However, this implementation runs into issues when there are cycles in the graph. Is there a better way of doing this?

edit: Assuming n nodes, there will never be more than 10n connections total.

Text

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ That looks too close to the directed hamiltonian path/cycle problem for confidence in a simple, efficient solution... $\endgroup$
    – vonbrand
    Commented Mar 12, 2020 at 1:07
  • $\begingroup$ What do you mean by "[w]e are allowed to take the same path twice"? $\endgroup$
    – xskxzr
    Commented Mar 12, 2020 at 1:42

1 Answer 1

Reset to default
1
$\begingroup$

Build the metagraph of strongly connected components. Then execute your idea on the metagraph. Note that once you enter a strongly connected component through any in-edge, you can collect all coins within it and leave through any out-edge out of that component.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Of course! SCCs, that makes complete sense, thank you very much! $\endgroup$
    – SopitaBanon
    Commented Mar 12, 2020 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.