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