Need help in problem 543B (Destroying Roads)

Revision en1, by kipawa, 2015-12-14 21:01:11

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!

Tags help, shortest path, wrong answer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English kipawa 2015-12-14 21:04:15 1 Tiny change: '>\n<a href"http://co' -> '>\n<a href="http://co'
en2 English kipawa 2015-12-14 21:03:42 104
en1 English kipawa 2015-12-14 21:01:11 1098 Initial revision (published)