I was trying out the problem <a href="http://mirror.codeforces.com/problemset/problem/543/B">Destroying Roads</a>. I am getting WA on test 16 but I cannot figure out whats wrong with my logic. Please help me out<br>↵
I am searching for any node <i>i</i> such that distance from s1 to t1 through <i>i</i> is feasible, i.e dis[s1][i]+dis[i][t1]<=l1 and dis[s2][i]+dis[i][t2]<=l2.<br>↵
Now once I get any such <i>'i'</i>, I try to figure out the value of <i>i</i> such that above condition holds and the the distance from s1 to t1 via <i>i</i> and from s2 to t2 via <i>i</i> is minimum.<br>↵
To calculate that distance, I construct the shortest path tree with source as <i>'i'</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. <br>↵
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. <br>↵
Please help me out!<br>↵
<a href"http://mirror.codeforces.com/contest/543/submission/14804538">My code</a><br>↵
Thanks in advance!
I am searching for any node <i>i</i> such that distance from s1 to t1 through <i>i</i> is feasible, i.e dis[s1][i]+dis[i][t1]<=l1 and dis[s2][i]+dis[i][t2]<=l2.<br>↵
Now once I get any such <i>'i'</i>, I try to figure out the value of <i>i</i> such that above condition holds and the the distance from s1 to t1 via <i>i</i> and from s2 to t2 via <i>i</i> is minimum.<br>↵
To calculate that distance, I construct the shortest path tree with source as <i>'i'</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. <br>↵
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. <br>↵
Please help me out!<br>↵
<a href"http://mirror.codeforces.com/contest/543/submission/14804538">My code</a><br>↵
Thanks in advance!
