Sachverhalt: Sachverhalt: A. V._ war seit dem 1. Januar 1995 beim Strassenverkehrs- und Schifffahrtsamt des Kantons Nidwalden tätig. Am 26. Mai 1999 wurde ihm die Kündigung des Arbeitsverhältnisses auf den 30. September 1999 eröffnet. Hiergegen erhob er am 16. Juni 1999 Einsprache beim Regierungsrat des Kantons Nidwalden mit dem Antrag, die Kündigung aufzuheben. In seiner Replikschrift vom 27. Juli 1999 erklärte V._, er akzeptiere zwar die Auflösung des Arbeitsverhältnisses, da er eine neue Stelle gefunden habe, ziehe aber seine Einsprache wegen der noch offenen Lohn- und Entschädigungsansprüche nicht zurück. Der Regierungsrat wertete diese Erklärung als faktischen Rückzug der Einsprache und schrieb diese am 19. Oktober 1999 vom Protokoll ab, da über die geltend gemachten finanziellen Ansprüche nicht im Einspracheverfahren zu befinden sei. V._ erhob gegen den Regierungsratsbeschluss am 15. November 1999 Beschwerde beim Verwaltungsgericht des Kantons Nidwalden, welches diese mit Urteil vom 28. August 2000 jedoch abwies. Das Urteil des Verwaltungsgerichts wurde vom Bundesgericht auf Beschwerde von V._ hin am 22. Dezember 2000 aufgehoben. Das Urteil des Verwaltungsgerichts wurde vom Bundesgericht auf Beschwerde von V._ hin am 22. Dezember 2000 aufgehoben. B. Das Verwaltungsgericht des Kantons Nidwalden behandelte in der Folge die Beschwerde vom 15. November 1999 erneut. Mit Urteil vom 25. April 2001 hiess es die Beschwerde gut, hob den Beschluss des Regierungsrats vom 19. Oktober 1999 auf und wies die Sache zur Neubeurteilung an diesen zurück. V._ erhob auch gegen dieses Urteil staatsrechtliche Beschwerde, weil ihm keine Parteientschädigung zugesprochen worden sei. Er beantragte, das Urteil im betreffenden Punkt (Dispositiv Ziff. 3) aufzuheben und die Sache zur Zusprechung einer Vergütung an das Verwaltungsgericht zurückzuweisen. Das Bundesgericht trat auf die Beschwerde nicht ein, weil der Beschwerdeführer den Kostenvorschuss nicht geleistet hatte (Art. 150 Abs. 4 OG; Urteil (des Bundesgerichts) 2P.189/2001 vom 3. September 2001). Das Bundesgericht trat auf die Beschwerde nicht ein, weil der Beschwerdeführer den Kostenvorschuss nicht geleistet hatte (Art. 150 Abs. 4 OG; Urteil (des Bundesgerichts) 2P.189/2001 vom 3. September 2001). C. Im Anschluss an das Urteil des Verwaltungsgerichts vom 25. April 2001 behandelte der Regierungsrat des Kantons Nidwalden seinerseits die Einsprache vom 16. Juni 1999 erneut, nunmehr materiell, und hiess sie mit Beschluss vom 21. Mai 2002 gut. Eine Parteientschädigung sprach er nicht zu, weil der Einsprecher im Einspracheverfahren (noch) nicht anwaltlich vertreten gewesen sei. Dieser Beschluss ist unangefochten in Rechtskraft erwachsen. C. Im Anschluss an das Urteil des Verwaltungsgerichts vom 25. April 2001 behandelte der Regierungsrat des Kantons Nidwalden seinerseits die Einsprache vom 16. Juni 1999 erneut, nunmehr materiell, und hiess sie mit Beschluss vom 21. Mai 2002 gut. Eine Parteientschädigung sprach er nicht zu, weil der Einsprecher im Einspracheverfahren (noch) nicht anwaltlich vertreten gewesen sei. Dieser Beschluss ist unangefochten in Rechtskraft erwachsen. D. V._ hat am 25. Juni 2002 gegen das Urteil des Verwaltungsgerichts vom 25. April 2001 erneut staatsrechtliche Beschwerde erhoben. Er beantragt, das Urteil "sei in Ziff. 3 (Verweigerung der Parteientschädigung) aufzuheben und in diesem Punkt an die Vorinstanz zurückzuweisen zum neuen Kostenentscheid mit Zusprechung einer angemessenen Vergütung an den Beschwerdeführer für dessen Vertretungskosten". Er macht eine Verletzung des Willkürverbots (Art. 9 BV) sowie seines Anspruchs auf rechtliches Gehör (Art. 29 Abs. 2 BV) geltend. Der Regierungsrat beantragt über seinen Rechtsdienst, die Beschwerde abzuweisen, sofern darauf einzutreten sei; auf eine Begründung seines Antrags verzichtet er. Das Verwaltungsgericht hat unter Hinweis auf das angefochtene Urteil auf eine Vernehmlassung verzichtet; ebenso das Strassenverkehrs- und Schifffahrtsamt. 