Блог пользователя Warriors_Cats

I want to ask a question about shortest paths!
Автор Warriors_Cats, история, 4 года назад, По-английски

Hello, guys! Can anyone suggest me an appropiate idea on this shortest path task: https://cses.fi/problemset/task/1203/? I have already exhausted all my efficient approaches on this topic. Any eligible answer would be appreciated! Thanks a lot!

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hello. lets call f(i, j) — shortest path from city i to city j. You have to print such cities z, that f(1, z) + f(z, n) = f(1, n).That's why all you have to do is to calulate f(1, i) and calculate f(i, n) for every i. you can calculate f(1, i) by running dijkstra from node 1 on the current graph.How to calculate f(i, n) in linear time?You just have to reverse all edges and run dijkstra from node n.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    I understand what you mean, but your approach will yield all of those vertices involved in the set of shortest paths between 1 and n, won't it? The task's query actually requests only those vertices shared by all shortest paths between city 1 and n. Do you see what I mean?

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    If I applied your idea on the given example, I would gain that even vertex 2 belongs to the final answer, which is false, because all the vertices shared by those two shortest paths existent in our graph (1->2->3->4->5 and 1->3->4->5) are 1,3,4 and 5 respectively.

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Did you mean something like this: https://pastebin.com/nt8cjsVU? This is my implementation based on your explanation, which receives Wrong Answer on 5 test cases from 13.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      no, I didn't red the statement carefully.

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        But i came up with this idea(which got AC). let's leave only such edges (u, v) that f(1, u) + price[(u, v)] + f(v, n) = f(1, n).After that let's make every edge undirected. We have to print node v if v is articulation point or v = n or v = 1.

        → Ответить
»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hi, so the solution is actually pretty straightforward.

  1. Build shortest path DAG using Dijkstra
  2. Do a topological sort
  3. Find dominators of target node using definition (look at algorithm section on https://en.wikipedia.org/wiki/Dominator_(graph_theory)). Note that the complexity will be linear since all predecessors of a node will already have been processed due to topological sort.
→ Ответить