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.
Erwägungen:
1.
Angefochten ist ein kantonal letztinstanzlicher Endentscheid in einer öffentlich-rechtlichen Angelegenheit (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Die Beschwerdeführer sind zur Beschwerde berechtigt (Art. 89 Abs. 1 BGG). Auf die Beschwerde ist einzutreten.
2.
Zur Begründung der Höhe der Gerichtskosten von Fr. 8'000.-- führte das Verwaltungsgericht aus, es sei zu berücksichtigen, dass das Urteil in Fünferbesetzung gefällt worden sei und deshalb ein erhöhter Aufwand resultiert habe. In Betracht falle sodann auch, dass am Verwaltungsgericht im Jahr 2015 der effektive Aufwand pro Fall im Mittel rund Fr. 9'500.-- betragen habe, wovon durchschnittlich nur ein Viertel durch die Gerichtsgebühren gedeckt worden sei. Nachdem sich das Beschwerdeverfahren gegenüber den meisten anderen als deutlich aufwendiger präsentiert habe, erscheine folglich eine Gerichtsgebühr von Fr. 8'000.-- als angemessen und würden die Prinzipien der Kostendeckung und Äquivalenz ohne Weiteres eingehalten.
3.
3.1. Die Beschwerdeführer kritisieren, das Verwaltungsgericht begründe nicht, weshalb durch die Fünferbesetzung im vorliegenden Fall ein höherer Aufwand resultiert habe. Namentlich mache es nicht geltend, es hätte eine mündliche Beratung, ein Meinungsaustausch, ein Beweisverfahren oder eine mündliche Verhandlung stattgefunden. In einem weitaus komplexeren Fall mit deutlich umfangreicheren Akten sei die Gerichtsgebühr auf lediglich Fr. 3'000.-- festgesetzt worden (Urteil des Verwaltungsgerichts des Kantons Zürich VB.2014.00523 vom 24. April 2015). Zudem sei zu berücksichtigen, dass gerade der Zugang zur abstrakten Normenkontrolle nicht übermässig erschwert werden dürfe. Wenn schliesslich die Gerichtsgebühren durchschnittlich nur rund einen Viertel der Aufwendungen des Gerichts ausmachten, diese im vorliegenden Fall aber fast gänzlich deckten, so stelle dies eine rechtsungleiche Behandlung dar.
3.2. Wie das Bundesgericht bereits im Urteil vom 12. Mai 2016 erläuterte, müssen Gerichtskosten dem Kostendeckungs- und Äquivalenzprinzip genügen, wobei das Äquivalenzprinzip bestimmt, dass eine Gebühr nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der Leistung stehen darf und sich in vernünftigen Grenzen halten muss. Bei der Beurteilung der Frage, welche Gerichtsgebühr für ein Verfahren angemessen erscheint, steht den kantonalen Gerichten ein grosser Ermessensspielraum offen, den das Bundesgericht respektieren muss. Es kann daher lediglich überprüfen, ob ein offensichtliches Missverhältnis zwischen der Gebühr und dem objektiven Wert der bezogenen Leistung besteht und sich die Gebühr in vernünftigen Grenzen bewegt (vgl. im Einzelnen Urteil 1C_50/2016 vom 12. Mai 2016 in der gleichen Angelegenheit, E. 3.2 mit Hinweisen). Das Bundesgericht hob den damals angefochtenen Kostenentscheid deshalb auf, weil das Verwaltungsgericht zu Unrecht auf die angebliche politische Bedeutung abstrakter Normenkontrollverfahren abgestellt hatte und die Gerichtskosten angesichts des durch den Fall verursachten Aufwands als klar übersetzt erschienen (a.a.O., E. 3.5).
3.3. Wie dem Urteil vom 12. Mai 2016 ebenfalls zu entnehmen ist, waren die im vorinstanzlichen Verfahren zu beurteilenden Rechtsfragen einerseits nicht einfach, andererseits aber auch nicht speziell komplex (a.a.O., E. 3.5). Wenn das Verwaltungsgericht in seinem neuen Entscheid festhält, das Beschwerdeverfahren sei gegenüber den meisten anderen deutlich aufwendiger gewesen, ist dies nicht zu beanstanden. Berücksichtigen durfte es auch, dass der Entscheid in Fünferbesetzung gefällt worden war. Dass sich der Aufwand für das Gericht dadurch erhöhte, versteht sich von selbst und muss nicht speziell begründet werden. Auch legte das Verwaltungsgericht entgegen den Vorbringen der Beschwerdeführer dar, dass eine mündliche Beratung stattgefunden hatte (a.a.O., E. 3.4), was sich ebenfalls in einem erhöhten Aufwand niederschlägt. Insgesamt erscheinen die von der Vorinstanz festgesetzten Gerichtskosten deshalb zwar nach wie vor als hoch, jedoch vor dem Hintergrund des den kantonalen Gerichten in diesem Zusammenhang zustehenden Ermessensspielraums nicht als offensichtlich unverhältnismässig. Die Rüge der Verletzung des Äquivalenzprinzips ist somit unbegründet.
3.4. Auch unter dem Gesichtspunkt der Rechtsgleichheit ist der angefochtene Entscheid nicht zu beanstanden. Wenn die Beschwerdeführer geltend machen, im vorliegenden Fall werde der durchschnittliche Aufwand mit der Gerichtsgebühr beinahe gedeckt, übersehen sie, dass insofern nicht der durchschnittliche, sondern der im konkreten Fall tatsächlich entstandene Aufwand massgebend ist. Schliesslich ist das von den Beschwerdeführern zum Vergleich herangezogene Urteil des Verwaltungsgerichts des Kantons Zürich VB.2014.00523 vom 24. April 2015 nicht gleich gelagert wie der vorliegende Fall. Jenes Urteil ist zum einen weniger umfangreich und wurde zum andern in Dreierbesetzung gefällt. Mithin gab es sachliche Gründe, in beiden Fällen die Gerichtsgebühren unterschiedlich hoch anzusetzen.
4.
Die Beschwerde ist aus diesen Gründen abzuweisen.
Bei diesem Verfahrensausgang sind die Gerichtskosten den Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 BGG). Es ist keine Parteientschädigung zuzusprechen (Art. 68 Abs. 1-3 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern auferlegt.
3.
Es wird keine Parteientschädigung zugesprochen.
4.
Dieses Urteil wird den Beschwerdeführern, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 13. Oktober 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Merkli
Der Gerichtsschreiber: Dold