پاسخ - SGU 103
متن اصلی سوال: http://acm.sgu.ru/problem.php?contest=0&problem=103
در شهر دینگیلی ، ترافیک به طور نامعمولی کنترل می شود . در این شهر تعدادی ایستگاه و تعدادی جاده که ایستگاه ها را به هم متصل کردند داریم . بین هر دو ایستگاه حد اکثر یک جاده وجود دارد و هیچ جاده ای ایستگاهی را به خودش متصل نمی کند . در هر ایستگاه یک چراغ وجود دارد که یا رنگ آن در هر لحظه آبی یا قرمز است . رنگ هر چراغ به صورت دوره ای همواره در حال عوض شدن است ، و برای مدت مشخصی آبی و بعد برای مدت مشخصی قرمز است و دوباره آبی ... . فقط در صورتی می توانیم از یک جاده عبور کنیم که در لحظه ای که می خواهیم حرکت را شروع کنیم رنگ چراغ ایستگاه های دو سر جاده یکسان باشد . اگر یک وسیله ی نقلیه درست در لحظه ای که رنگ چراغ ایستگاه تغییر می کند به یک ایستگاه برسد ، باید رنگ جدید چراغ را در نظر بگیریم . وسیله های نقلیه اجازه دارند در ایستگاه ها توقف کنند . به شما نقشه ی شهر داده شده :
- مدت زمانی که طول می کشد تا از هر جاده عبور کنیم
- مدت زمان هر دو رنگ برای چراغ هر ایستگاه
- رنگ اولیه و زمان باقی مانده برای تغییر این رنگ در هر ایستگاه
شما باید کوتاه ترین مسیر بین دو ایستگاه داده شده در ورودی را پیدا کنید . اگر بیش از یک جواب وجود داشت می توانید یکی را به دلخواه در خروجی چاپ کنید .
ورودی :
خط اول ورودی شامل شماره ی ایستگاه اولیه و ایستگاه مقصد است .
خط دوم ورودی شامل دو عدد N و M است (به ترتیب : تعداد ایستگاه ها ، تعداد جاده ها)
در N خط بعدی اطلاعات ایستگاه ها به ترتیب شماره آمده است . در خط i+2 ام Ci, riC, tiB, tiP آمده اند . Ci نشان دهنده ی رنگ اولیه چراغ ایستگاه است که B (برای رنگ آبی ) یا P (برای رنگ قرمز) است . riC زمان باقی مانده از دوره ی رنگ فعلی چراغ ایستگاه است و tiB, tiP به ترتیب مدت زمان دوره ی رنگ قرمز و رنگ آبی اند .
در M خط بعدی اطلاعات جاده ها آمده . هر خط شامل سه عدد i, j, lij که نشان دهنده ی وجود یک جاده بین دو شهر i و j است که عبور کردن از آن به انداره ی lij زمان می برد .
خروجی :
اگر مسیری بین دو شهر داده شده وجود داشت :
در خط اول خروجی زمان طی کردن کوتاه ترین مسیر را چاپ کنید و در خط بعدی لیست ایستگاه هایی که در کوتاه ترین مسیر طی می شوند را چاپ کنید (به ترتیب ظاهر شدن در مسیر )
اگر مسیری بین دو شهر وجود نداشت در خروجی عدد 0 را چاپ کنید .
راهنمایی :
از الگوریتم دایکسترا استفاده کنید .
ولی اینم کد من
http://paste.ubuntu.com/1491773/