پاسخ - SGU 226

متن اصلی سوال: http://acm.sgu.ru/problem.php?contest=0&problem=226

ترجمه :

گراف جهت دار G به شما داده شده است . هر یال آن با یکی از سه رنگ 1 و 2 و 3 رنگ شده است . از شما می خواهیم کوتاه ترین مسیر از راس 1 به راس n را طوری بیابید که هیچ دو یال متوالی در مسیر همرنگ نباشد.

ورودی :

در خط اول ورودی دو عدد N و M می آیند (N تعداد راس ها و M تعداد یال ها ).

در M خط بعدی مشخصات یال ها می‎آید . در هر خط سه عدد X و Y و C در می آیند. که X سر یال و Y انتهای یال است و C رنگ یال را مشخص می کند .



خروجی :
در تنها خط خروجی طول کوتاه ترین مسیر از راس 1 به راس n را چاپ کنید. اگر مسیری از راس 1 به راس n  وجود نداشت، عدد 1- را چاپ کنید.

---

راهنمایی:

از جستجوی نخست پهنا استفاده کنید .(یک کوچولو هم Dynammic می خواد.(

کد ++C

پ.ن : این پست رو آقای میلاد رضایی ارسال کردند. با تشکر از ایشون. :)