I was trying out the problem Destroying Roads. I am getting WA on test 16 but I cannot figure out whats wrong with my logic. Please help me out
I am searching for any node i such that distance from s1 to t1 through i is feasible, i.e dis[s1][i]+dis[i][t1]<=l1 and dis[s2][i]+dis[i][t2]<=l2.
Now once I get any such 'i', I try to figure out the value of i such that above condition holds and the the distance from s1 to t1 via i and from s2 to t2 via i is minimum.
To calculate that distance, I construct the shortest path tree with source as 'i' and then I calculate the above value via O(n) lca algorithm, i.e once the shortest path tree is created, I traverse from s1 to t1 keeping only that edges and from s2 to t2 keeping only that edges and deleting the other edges.
I tried many test cases and my code is working fine, but its giving WA on test 16, answer is 2942 but my code is giving 2941.
Please help me out!
My code
Thanks in advance!