I can see this having more of an effect for priests and advies than for troops as most regions only vary between needing a turn or two to cross. I would also add a point that detracts maintenance fees for these roads from taxes just as militia does and varied depending on the quality. They could even have tiers:
Lvl
1. Footpaths - Not so much a road as it is a route. Footpaths are unmapped and out of the way, causing significant delays in travel. (+2 hrs) (+10 gold)
2. Waggon Track - The path less-traveled, Wagon tracks are avenues of necessity for the peasantry and minor nobility, but suffer from ruts, holes, flooding, etc. (+1 hrs)(+0 gold)
3. Trade Route - An important, mapped byway, often including stylized road signs for ease of navigation. (-1 hrs)(-10 gold)
4. Kings Road - A well-paved, well-maintained, and well defended road initially planned and built by some nameless monarch as the best way through this region. (-2 hrs)(-20 gold)
