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] (https://i.gyazo.com/62d63e869824d44bf378bf908d2479c8.png)
