Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

c___a_'s blog

By c___a_, history, 14 months ago, ,

We are given 2 nodes s and t, and M queries that have one edge that needs to be deleted [only for this query], and for each query you need to output the shortest path between s and t. Note that s and t do not change.

1 ≤ Number of Nodes ≤ 7000

1 ≤ Number of edges ≤ 50000

1 ≤ Number of queries ≤ 10000

I couldn't find anything over the internet. I was thinking of something along the walks of pre-computation on a Dijkstra tree/Shortest path tree but couldn't think of anything. Can someone please provide hints or an approach to this problem?

•
• +28
•

 » 14 months ago, # |   0 Does deletion means turning weight to 0 and keeping the edge or complete removal of the edge?
•  » » 14 months ago, # ^ |   0 Completely removing the edge.
 » 14 months ago, # |   0 I dont know how MaxFlow/Min Cut works. But this link may help you https://stackoverflow.com/questions/10895259/shortest-path-in-absence-of-the-given-edge
•  » » 14 months ago, # ^ |   0 I've seen that link, but there exists a much simpler solution not involving Max Flow/Min Cut I believe
•  » » » 14 months ago, # ^ |   +1 The word "cut" does not mean that you need some mincut algorithm. Let's explain it in other words.For a given edge e we can define two sets of edges: and . path(x, y) is some shortest path between x and y. We will assume that , otherwise the answer is obvious.It's easy too see that each vertex lies either in A or in B. Consider the earliest moment when we go from the vertex in to the vertex in . By definition, we can go from s to x by the shortest path in the original graph, the same is true for y and t. So the path is uniquely determined by the edge xy. We just need to go through all edges xy such that and .It works in O(qm) for queries and for shortest paths precomputations. Also there is a way to sped up it to .
•  » » » » 14 months ago, # ^ |   0 That makes sense, I understand your solution, thanks! But for each such edge xy, we have to iterate through all edges in our shortest path and update the answer for this edge in our pre-computation right? Doesn't that make the complexity O(M*N) rather than O(MlogM)? [since there can be at most N edges in the shortest path]
•  » » » » » 14 months ago, # ^ |   +1 No, for each edge xy we just use precomputed values of d(s, x) and d(y, t) in the original graph.
•  » » » » » » 14 months ago, # ^ |   0 Couldn't the path d(s,x) -> edge xy -> d(y,t) be an answer for all edges in our shortest path d(s,t)? So we're iterating through all such edges xy and updating the answer for all edges in our shortest path during pre-computation, right?
•  » » » » » » » 14 months ago, # ^ |   +1 No, in precomputation we only build two Dijkstra trees, from s and from t. We need them to find sets A and B.For each query we find A and B, iterate through edges, and find the answer.
•  » » » » » » » » 14 months ago, # ^ |   0 But won't O(qm) time out for the given constraints?
 » 14 months ago, # |   0 Isn't this the Facebook problem from ioitc 2012?!
•  » » 14 months ago, # ^ |   0 Yup, it is the same problem and same constraints.
 » 14 months ago, # | ← Rev. 3 →   +1 Since answer for edges not on original shortest path is the same, ignore those.Consider the dijkstra/shortest path tree of the graph from s. In this, if you delete an edge on the shortest path to t, the tree splits into 2 parts, if you can appropriately find the "bridge" between these 2 components, you can solve the problem.For finding that, consider an edge (u, v, d) not in the original dijkstra tree. Assume in the dijkstra tree , The shortest path going via this edge has weight D(s, u) + D(v, t) + d where D(a, b) = distance b/w nodes.So this edge may form the shortest path bridge when we disconnect some other edge on path(u, v) in the tree. This reduces the problem to path update + edge query, which can be handled offline(or with HLD).Time complexity: O((N + M)·log(N + M) + Q)
•  » » 14 months ago, # ^ |   0 Thanks! But how do you handle offline processing efficiently? I can't think better than O(M*N)
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +1 You can just use straightforward HLD.Or, since you only need to worry about edges on path s -> t, this is equivalent to saying you have an array of edges b/w s to t sequentially(each having value infinity) and some range updates (L, R, w) which describe “set the value of all elements between (L,R) to min(current value, w)”, this can be done using set or something and iterating from left to right, activating and deactivating the updates.
•  » » » » 14 months ago, # ^ |   0 I think I understand. But suppose we have an edge (u,v,d) : how do we decide the (L,R) values [or the sequential edges] in our linear path that this edge can affect?