Sachverhalt: A. Am 29. April 2015 beschloss der Regierungsrat des Kantons Zürich eine Änderung der kantonalen Bauverfahrensverordnung vom 3. Dezember 1997 (BVV; LS 700.6). Gegen diesen Beschluss erhoben A._ und die B._ AG Beschwerde beim Verwaltungsgericht des Kantons Zürich. Mit Urteil vom 3. Dezember 2015 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat. Die Gerichtsgebühr von Fr. 12'000.-- auferlegte es den Beschwerdeführern je zur Hälfte und unter solidarischer Haftung. Dagegen erhoben A._ und die B._ AG am 29. Januar 2016 Beschwerde beim Bundesgericht und beantragten eine Reduktion der Gerichtsgebühr. Mit Urteil 1C_50/2016 vom 12. Mai 2016 hiess das Bundesgericht die Beschwerde gut und hob den vorinstanzlichen Kostenentscheid auf. Das Verwaltungsgericht nahm das Verfahren in der Folge wieder auf. Mit Urteil vom 9. Juni 2016 setzte es die Gerichtsgebühr auf Fr. 8'000.-- herab. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht vom 27. Juli 2016 beantragen A._ und die B._ AG erneut die Aufhebung des verwaltungsgerichtlichen Kostenentscheids. Die Gerichtsgebühr sei auf maximal Fr. 4'000.-- zu reduzieren. Eventualiter sie die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Der Regierungsrat hat auf eine Vernehmlassung verzichtet.