Let $R$ be the set of all routes from $A$ to $B$. For each route we take the very first toll road and give it to company $C_1$, so clearly every car that goes from $A$ to $B$ has to pay a toll to $C_1$. Suppose $C_1$ makes all its toll roads free and now there exists a route, $r$, from $A$ to $B$ that has $8$ or less toll roads. This means that the route $r$ contains at least $2$ toll roads that belong to $C_1$, however the very last toll road on the route that belongs to $C_1$ is also the first toll road of some other route, $r'$ (because of how we selected $C_1$). Now route $r'$ goes through at most $9$ toll roads which contradicts our original assumption. Hence each route from $A$ to $B$ still goes through at least $9$ toll roads that do not belong to $C_1$. Now we can continue this process giving the first toll road from each route that doesn't already blong to $C_1$ to $C_2$ etc. Such that $10$ companies all own toll roads on every route from $A$ to $B$ $\square$

Let the southern capital be $A$ and the northern one be $B.$ For each town/capital in the country, label it with the number $x \ge 0$ which is the minimum number of toll roads one must use to travel from $A$ to this town. A few observations follow. Observation 1. Any two cities with are connected with a road and have different labels must be connected with a toll road. Proof. If one has a greater label than the other and the road connecting them isn't a toll road, then we can travel first to the town with smaller label with the minimum possible number of toll roads, then travel directly to the other town. This is a contradiction. $\blacksquare$ Observation 2. Any two cities connected with a toll road have labels differing by at most $1.$ Proof. Proof similar as the above proof (suppose that one has label greater than the other one by at least $2$). $\blacksquare$ With the above observations, we are ready to finish. For $0 \le i \le 9$, if a toll road connects two cities with labels $i$ and $i+1$, then we grant this road to company $i$. All other toll roads (which must connect two cities with the same label) are distributed arbitrarily amongst the companies. We claim that this works. Indeed, consider some path from $A$ to $B.$ Since the label of $B$ is at least $10$, for each $0 \le i \le 9$, there must be a town on the path which has label $i+1$ (by Observations $1, 2$, the labels of adjacent vertices differ by at most one), and so the road leading into this town must be a toll road belonging to company $i$ (Observations $1, 2$). This concludes the proof. $\square$