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!! :)