### I_dont_have_girlfriend's blog

By I_dont_have_girlfriend, 11 years ago,

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 :-)

 » 11 years ago, # |   0 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
•  » » 11 years ago, # ^ | ← Rev. 3 →   +5 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