Ada in Dreamland

You are given a graph and asked if there is any node u such that:

• u is part of a cycle where the multiplication of the edges of the cycle has value strictly less than 1. (Ada can traverse this cycle infinite times and have a reading which tends to zero.)
• u is reachable from 1 and n is reachable from u.

A DFS is enough for the latter.

For the former, you have to check if there exists some cycle like that. Notice that $ \log (x) = (-ve) $ where $ 0 < x < 1 $. Lets convert the edge weights to their log values in any suited base. Since $ \log (UV) = \log U + \log V $, our sub-problem is now reduced to finding a cycle with negative sum. This can be done with Bellman–Ford algorithm under the given constraints.

So our solution skeleton would be like this:

• Convert the edge weights to their log values in any base.
• Run bellman ford to find which nodes are part of a negative cycle.
• Check if n is reachable from any of those nodes, if any. Also check if those nodes are reachable from 1.

Should you need it, find my C++ implementation here: https://gist.github.com/rebornplusplus/3b8d22de1e8a1b7f4419ef053c8e0500.

P.S: The initial reading d doesn't do much. I thought you could use a joke. 😛