Faits: A. A.X._ et B.X._ sont propriétaires du bien-fonds no xxx du cadastre de Chézard-St-Martin sur lequel se trouve leur maison. La parcelle est desservie au sud par la rue D._. Le 30 juin 2003, C._ SA a déposé une demande portant sur la construction de quatre immeubles résidentiels de trois lofts chacun et sept villas individuelles avec garage à l'est de la parcelle des époux X._, dans le prolongement de la rue D._. L'enquête publique effectuée à la suite de la demande du permis de construire a été publiée deux fois dans la Feuille officielle, soit les 28 mai et 4 juin 2004. Le 23 juin 2004, B.X._ a adressé une lettre au Conseil communal de Chézard-St-Martin (ci-après le Conseil communal). Déclarant ne pas s'opposer aux travaux prévus, mais craignant pour la résistance de la route et partant pour son immeuble, il demandait qu'un constat des lieux soit établi avant la mise en chantier et que les éventuels dégâts dus au passage de poids lourds devant son domicile soient pris en charge par le maître d'oeuvre. Une séance de conciliation s'est tenue le 16 août 2004 entre les promoteurs, les opposants, le Conseil communal et B.X._, qui n'apparaissait pas comme opposant. Le 14 octobre 2004, le Conseil communal a envoyé une lettre à B.X._, lui expliquant que l'accès au nouveau lotissement par la rue D._ ne durerait que le temps des travaux et qu'il était certain que ce chemin serait à terme remplacé, comme seul accès aux nouvelles habitations, par la nouvelle route qui serait construite après la levée des oppositions et la liquidation des éventuelles procédures d'expropriation. Lors d'une séance extraordinaire du 30 octobre 2006, le Conseil communal a rappelé que l'autorisation de construire le nouveau quartier était liée à la réalisation de la nouvelle route. Lors d'une séance du 27 avril 2009, le Conseil communal a relevé que, compte tenu des implications financières, des procédures juridiques longues et incertaines et d'un renforcement des exigences en matière de zone à bâtir et d'utilisation du sol, la Commune n'avait pas d'assurance légale de construire cette nouvelle route. Le 9 novembre 2009, la Commune a adopté un arrêté limitant la vitesse maximale à 20 km/h sur la rue D._, donnant la priorité aux piétons, restreignant le parcage aux endroits prévus et prévoyant que ce chemin serait signalé comme sans issue. Le recours formé par B.X._ contre cet arrêté a été rejeté, le 8 septembre 2011, par le Département de la gestion du territoire du canton de Neuchâtel. A.X._ et B.X._ ont mandaté un expert pour déterminer la dépréciation de leur immeuble en raison de l'accès au nouveau lotissement, qui l'a chiffrée à 117'000 fr. B. Le 5 décembre 2011, les époux X._ ont formé une demande d'indemnisation auprès de la Commune. Le Conseil communal a répondu, le 8 mars 2012, qu'il ne pouvait y être donné suite. Le 12 juin 2012, A.X._ et B.X._ ont ouvert action devant la Cour de droit public du Tribunal cantonal neuchâtelois (ci-après le Tribunal cantonal), concluant au versement par la Commune de 117'000 fr. plus intérêt à 5 % l'an dès le 7 février 2011 à titre d'indemnisation. Ils ont fait valoir en substance que le Conseil communal leur avait affirmé qu'une nouvelle route serait réalisée pour accéder au nouveau lotissement et que le nouveau quartier n'engendrerait aucun désagrément. Sur la base de ces promesses, ils n'avaient pas recouru contre l'autorisation de construire délivrée à C._ SA. Or, finalement, le Conseil communal avait changé d'avis pour des raisons purement économiques, ce qui avait entraîné une dépréciation de leur bien-fonds. Ils estimaient que ce changement d'avis, malgré les garanties fournies, était contraire à la bonne foi et constituait un comportement illicite. Par arrêt du 28 mai 2013, le Tribunal cantonal a rejeté la demande. C. Contre cet arrêt, A.X._ et B.X._ forment un recours en matière de droit public auprès du Tribunal fédéral. Invoquant l'arbitraire et une violation de leur droit d'être entendu, ils concluent à l'annulation de l'arrêt du 28 mai 2013 et au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des motifs de leur recours. Ils demandent par ailleurs la production des dossiers cantonaux. Le Tribunal cantonal n'a pas formulé d'observations, se référant aux motifs de l'arrêt attaqué et concluant au rejet du recours. Dans ses déterminations, la Commune a précisé que, depuis le premier janvier 2013, elle avait fusionné avec diverses autres communes et formait désormais avec ces entités la Commune du Val-de-Ruz, qui était de ce fait la partie intimée à la présente procédure. Sur le fond, elle propose le rejet du recours.