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!