I need help with problem Intercity from SEERC 2013. link to problem
Could anyone provide some insight? Thank you!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I need help with problem Intercity from SEERC 2013. link to problem
Could anyone provide some insight? Thank you!
Name |
---|
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.