Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

PlayLikeNeverB4's blog

Graph problem
By PlayLikeNeverB4, 13 years ago, In English

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

Could anyone provide some insight? Thank you!

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

»
13 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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!

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

      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.

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

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

      → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Never mind.

→ Reply