I recently encountered this problem (from Balkan OI 2012)
https://www.acmicpc.net/problem/5250
..and I have absolutely no idea except the naive algorithm of O(nmlgm).
Any hints or solution for this problem? Is this problem utilizes some data structures that is less known?
we can get shortest path from a with mlgn let's call it dis1
we can also get the shortest path from b with mlgn let's call it dis2
lets sort the vertices by their distance from a and call it sorted
so we are removing an edge lets call the one that has less distance from a, u, and the other v in every path from a to b there's always some edge that starts before v and ends after u(in sorted array) we know that if we use this edge and the path(the one we are talking about) is a shortest path we wont use uv (is this correct? idk) so for every edge that has these properties we just calculate
dis1[first_one] + weight + dis2[second_one] we want the minimum of these
there are at most n edges to remove and we check m edges for them which is of O(nm) so overall order is of O(nm + mlgn) = O(nm) correct me if i'm wrong
I finally managed to solve this question with a big help from ainta and .o.. I also want to thank for the comment of Reyna :)
Here's the algorithm which solves this problem :
to prove this algorithm's correctness, observe that the shortest path 1 — u will never go via LCA(1,u) ~ LCA(1,v)
this algorithm doesn't necessarily require the computation of LCA — it can be replaced by simple dfs. it's naive implementation is O(NM) (which gives answer enough fast), but we can make a speedup by using segment tree or plane sweeping (via heaps or bst). So, this algorithm's time complexity is O(MlgM).
your welcome :D (i don't think my comment was useful though because it doesn't seem like the actual solution)
** Edited the image **
Sorry for replying to this old thread, but I am currently solving the same problem and it seems to me that there is a small flaw in your logic. Consider the following picture:
Say that we have decided that our path after removing some edge from the lucky path will go through edge (u, v). We find u' and v' (u' and v' are lca(u, e) and lca(v, e) respectivelly in the dijkstra tree of u). We then update our data structure (for example a segment tree with lazy propagation) from label[u] to label[v-1] with the weight of the path that passes through the edge (u, v). Specifically this weight, according to your post, must be equal to s-->u'-->u + (u, v) + v-->v'-->e. But how can we be sure that the blue or the green path in the image doesn't have smaller weight than the path e-->v'-->v. It seems to me that it is possible that blue_weight < v-->v'-->e or green_weight < v-->v'-->e. Am I correct on that?
Yes. It might have smaller weight. But, above algorithm will also process those blue and green edges. So the smaller weight will be applied there.
Removing road doesn't make everything that hard. Try removing vertex ;) (it is still doable).
The shortest path problem about removing vertex is here (Wuhan 2009): Live Archive 4491.