Faits: A. Par jugement par défaut du 20 mai 2010, publié dans la Feuille officielle cantonale, le Tribunal de police du district de Neuchâtel a acquitté X._ et Y._. Celui-là était accusé de faux dans les certificats, subsidiairement violation de l'art. 118 LEtr, et d'escroquerie, celle-ci d'escroquerie. Le 29 août 2011, les prénommés ont adressé au Tribunal de police une demande d'indemnité fondée sur l'art. 429 CPP. Par décision du 31 août 2011, le tribunal a rejeté la demande d'indemnité. B. Par jugement du 23 mars 2012, la Cour pénale du Tribunal cantonal neuchâtelois a admis l'appel de X._ et Y._, annulé la décision du 31 août 2011, et transmis la demande d'indemnité du 29 août 2011 au Département de la justice, de la sécurité et des finances du canton de Neuchâtel. En substance, la cour a considéré que la demande d'indemnité était régie par l'ancien art. 272 du Code de procédure pénale neuchâtelois (CPP/NE), qui renvoyait aux art. 11 et 21 de la Loi cantonale sur la responsabilité des collectivités publiques et de leurs agents (LResp/NE). La compétence pour traiter la demande d'indemnité relevait du département et non du tribunal de police. Il se justifiait dans ces conditions d'annuler la décision du tribunal de police et de transmettre la demande au département. C. X._ et Y._ forment un recours en matière pénale au Tribunal fédéral contre ce jugement et concluent, sous suite de dépens, principalement à ce que le Tribunal fédéral statue au fond sur la demande d'indemnité du 29 août 2011, subsidiairement à l'annulation du jugement et au renvoi en instance cantonale. Ils forment par ailleurs un recours constitutionnel subsidiaire dans lequel ils prennent des conclusions identiques. Le ministère public a conclu au rejet du recours. La cour cantonale ne s'est pas déterminée. 