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

Graph problem
Автор PlayLikeNeverB4, 11 лет назад, По-английски

I need help with problem Intercity from SEERC 2013. link to problem

Could anyone provide some insight? Thank you!

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

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

As far as i remember, an optimal solution always consists of only either new or old edges. It can be proved like this: the edge between the first and the N'th city is either new or old(for our convenience, let's think, that it is old). So, this edge is a way from the first to the N'th city. If there is another way, that contains an old edge, then it isn't shorter than just an old edge from 1 to N.

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

    Thanks for the tip. It's easy to find the best path using new edges. But I'm having difficulties finding the best path for old edges, because there are a lot of them. A little more help?

    Edit: Nevermind, I got it. I ended up running Dijkstra and using a segment tree for storing and updating the node costs. What a strange problem! Thanks for your help!

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

      Well, you can do it without any using Dijkstra algorithm.

      You just can do the following: place all the nodes into a set U(except the first node). The first node we put into a queue Q. Formally, in U we store all unvisited nodes. So, then let's start BFS algorithm from the first node, doing the following: let's check all the nodes in U and, if there is no edge between nodes, that we are considering, let's mark a node as "visited", remove it from U and add to our queue.

      Why it works fast? Because we will fail to mark a node as "visited" exactly M times.

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

      How did you updated N costs (equals B) which can have K costs (equals A)?

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

        For each node, I sorted it's new edges by their endpoints. Let's call them e1, e2, ..., ep. If the current cost is C then you have to update every valid interval [1,e1-1], [e1+1, e2-1], ..., [ep+1,N] with the cost C+1.

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

Never mind.

→ Ответить