Faits: A. Le 30 juin 2008, le Conseil général de la Ville de Neuchâtel a adopté un arrêté concernant le stationnement sur le domaine public. Cet arrêté prévoit en substance de limiter dans le temps le stationnement des véhicules, notamment par la création de zones de parcage avec disque. Des autorisations de stationnement de durée illimitée peuvent cependant être accordées au prix de 110 fr. par année aux résidents et aux entreprises ayant leur siège social dans la commune. Les "pendulaires dynamiques" pourront aussi bénéficier d'une autorisation de stationnement, au tarif annuel de 1'400 fr. pour une autorisation valable du lundi au vendredi ou de 1'600 fr. s'ils souhaitent stationner du lundi au samedi (art. 4 al. 4 et 7 al. 3 de l'arrêté du Conseil général). Le 1er décembre 2008, l'arrêté en question a été "sanctionné" - c'est-à-dire approuvé - par le Conseil d'Etat du canton de Neuchâtel (ci-après: le Conseil d'Etat), conformément à l'art. 8 de la loi cantonale du 21 décembre 1964 sur les communes (LCo; RSN 171.1). Les 8 et 11 décembre 2008, le Conseil communal de la Ville de Neuchâtel a adopté deux arrêtés précisant les conditions d'octroi des autorisations de stationnement de durée illimitée. Le premier arrêté concerne l'octroi de vignettes de stationnement et le second la perception des redevances de stationnement. Le Conseil d'Etat a "sanctionné" ces arrêtés le 1er juillet 2009. B. Le 1er juillet 2009 également, le Conseil d'Etat a adopté un arrêté modifiant de la manière suivante l'article premier de l'arrêté d'exécution de la loi d'introduction des prescriptions fédérales sur la circulation routière (RSN 761.100; ci-après: ALILCR): "1[inchangé] Les Conseils communaux peuvent interdire, restreindre et régler la circulation sur toutes les routes sises à l'intérieur de l'agglomération communale, sous réserve de l'approbation du service des ponts et chaussées. 2Toutefois, dans les zones soumises à stationnement limité, les titulaires de fonctions publiques de l'Etat de Neuchâtel qui, pour exercer ces dernières, ont un besoin indispensable d'un véhicule, sont assimilés aux habitants domiciliés dans la zone considérée, que le véhicule soit ou non immatriculé au nom de l'employeur. 3Le Conseil d'Etat fixe la liste des titulaires concernés. 4[Alinéa 2 actuel.]" Cet arrêté a été publié dans la Feuille officielle du canton de Neuchâtel du 3 juillet 2009. C. Agissant par la voie du recours en matière de droit public, les communes de Neuchâtel, de la Chaux-de-Fonds et du Locle demandent au Tribunal fédéral d'annuler l'arrêté précité du 1er juillet 2009. Elles invoquent la violation de l'autonomie communale, ainsi que des principes de la séparation des pouvoirs, de la légalité, de l'égalité de traitement et de la bonne foi. Le Conseil d'Etat conclut à l'irrecevabilité du recours, subsidiairement à son rejet. Au terme d'un second échange d'écritures, les parties persistent dans leurs conclusions. 