I need help with problem Intercity from SEERC 2013. link to problem
Could anyone provide some insight? Thank you!
I need help with problem Intercity from SEERC 2013. link to problem
Could anyone provide some insight? Thank you!
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | Kevin114514 | 3678 |
| 3 | VivaciousAubergine | 3647 |
| 4 | jiangly | 3582 |
| 5 | strapple | 3515 |
| 6 | tourist | 3473 |
| 7 | Radewoosh | 3418 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | turmax | 3345 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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.
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!
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.
Yep, your approach is definitely easier. Thanks :)
How did you updated N costs (equals B) which can have K costs (equals A)?
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.
Never mind.