[Kankuro]

Between Passau (Germany-Austria border) and Vienna, you have asphalt for most of it, with some unpaved/compacted parts (it may have improved since 2015). You need to cross the river by small boats (for a fee) a few times. For bicycle touring, checking the type of surface on OpenStreetMap beforehand can be quite useful. Travelling on unpaved paths is not at all as fast as on asphalt is you have an hybrid bike (my case).

[mariusor]

I would add that even farther East than that, the Czech Republic, Slovakia and Hungary have decent infrastructure for cycling long distances.