Warriors_Cats's blog

I want to ask a question about shortest paths!
By Warriors_Cats, history, 4 years ago, In English

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!

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

Comments Comments (10)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

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

    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?

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

    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.

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

    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.

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

      no, I didn't red the statement carefully.

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

        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.

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

          Articulation point using Tarjan's algorithm?

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

          СПАСИБО МНОГО ЧЕЛОВЕКА! Вы спасли мой день! ДА БЛАГОСЛОВИТ ВАС БОГ МОЙ ДРУГ!

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

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.
→ Reply