About exponentiation-distance on DAGs

About exponentiation-distance on DAGs

Hello everyone!!!

For a long long time, I have been struggling to do this problem: link to Online Judge (13143-Dijkstractions). I could not find any information or code on the internet.

In short, the problem is: given a DAG (Directed Acyclic Graph) and two nodes u, v, find the longest path from u to v, but with exponentiation-distance, i.e. if you have two edges a and b, the distance is not a+b but a^b (^ of exponentiation).

If there are multiple answers, then you have to return the one with the lowest lexicographical order.

What I have thought:

1- Maybe the part of returning the lowest lexicographical order path is not important, and you get it easy once you have the longest path.

2- I know how to solve this problem if it had sum-distance: Using tree (DAG) DP.

3- I know how to solve this problem if it had multiplication-distance: Changing the value of edges to log(edges) and using sum-distance. This is because if the longest path has 3 edges a1, a2, a3, a1*a2*a3 = ans => log(a1) + log(a2) + log(a3) = log(ans), and the path will be the longest in the new problem.

4- I have thought about how could I simplify the exponentiation-distance problem to multiplication-distance problem, similar to the 2-3 parts.

Can anyone provide a hint or a solution?

Thank you!! :)