Hello everyone!!!↵
↵
For a long long time, I have been struggling to do this problem: [link to Online Judge](https://onlinejudge.org/external/131/13143.pdf) (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!! :)
↵
For a long long time, I have been struggling to do this problem: [link to Online Judge](https://onlinejudge.org/external/131/13143.pdf) (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!! :)
