ko_osaga's blog

Stuck with some shortest path problems (from Balkan OI 2012)
By ko_osaga, 10 years ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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 :

  1. Run dijkstra algorithm from s and e
  2. Make a dijkstra tree which starts at s and contains the given route.
  3. the LCA of i and e will always exist in the given route. Let label[i] => the index of LCA(i,e) in the given route.
  4. let opt[i] as the answer of this problem. initialize it to infinity, and for every edge u,v which is not in the given route, update from opt[label[u]] ~ opt[label[v]-1] as dist(s,u) + dist(u,v) + dist(v,e)
  5. print opt[i] from range 1 ~ k-1.

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).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    your welcome :D (i don't think my comment was useful though because it doesn't seem like the actual solution)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    ** 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?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Removing road doesn't make everything that hard. Try removing vertex ;) (it is still doable).

→ Reply