Hello everybody,
I'm trying to solve this problem. But I don't have any ideas. Can someone help me, pls ?
Thanks!
UPD: I solved it :-)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello everybody,
I'm trying to solve this problem. But I don't have any ideas. Can someone help me, pls ?
Thanks!
UPD: I solved it :-)
Name |
---|
Wow, congratulations for solve this problem, I've already blogged here about this problem, but my doubts wasn't full cleared, could you explain your ideas to me ?
My Post
Hi, This problem can be solved using Dijkstra. Let's take a look at group of 3 continous vertices (u_1 -> u -> u_2), the tax equals max(Cost[u_1][u], Cost[u][u_2]).
So with any vertices, I have COST is the minimal amount of tax we have to pay, LAST is the tax of the last edge that we enter the town. Suppose I'm at the two [u] I update the result to the town [v] which is connected with [u] by a road (There are 2 cases: Cost[u][v] > LASTs and Cost[u][v] < LAST).
Beause the tax depends on vertices, it's not hard to understand that if d[u] is the minimal amount of tax to go to the town [u] and we haven't determined d[v], certainly, d[v] = d[u] + tax[v]. So after update [u][v], we can remove the road that connects [u] and [v].
My English isn't good, so I hope you can understand it :-)
My implementation http://ideone.com/eKdUIT