Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger
طبقه بندی موضوعی
پیوندهای روزانه

۱ مطلب با کلمه‌ی کلیدی «دایکسترا» ثبت شده است

۱۳دی

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

ترجمه :

در شهر دینگیلی ، ترافیک به طور نامعمولی کنترل می شود . در این شهر تعدادی ایستگاه و تعدادی جاده که ایستگاه ها را به هم متصل کردند داریم . بین هر دو ایستگاه حد اکثر یک جاده وجود دارد و هیچ جاده ای ایستگاهی را به خودش متصل نمی کند . در هر ایستگاه یک چراغ وجود دارد که یا رنگ آن در هر لحظه آبی یا قرمز است . رنگ هر چراغ به صورت دوره ای همواره در حال عوض شدن است ، و برای مدت مشخصی آبی و بعد برای مدت مشخصی قرمز است و دوباره آبی ... .  فقط در صورتی می توانیم از یک جاده عبور کنیم که در لحظه ای که می خواهیم حرکت را شروع کنیم رنگ چراغ ایستگاه های دو سر جاده یکسان باشد . اگر یک وسیله ی نقلیه درست در لحظه ای که رنگ چراغ ایستگاه تغییر می کند به یک ایستگاه برسد ، باید رنگ جدید چراغ را در نظر بگیریم . وسیله های نقلیه اجازه دارند در ایستگاه ها توقف کنند . به شما نقشه ی شهر داده شده :

  • مدت زمانی که طول می کشد تا از هر جاده عبور کنیم
  • مدت زمان هر دو رنگ برای چراغ هر ایستگاه
  • رنگ اولیه و زمان باقی مانده برای تغییر این رنگ در هر ایستگاه

شما باید کوتاه ترین مسیر بین دو ایستگاه داده شده در ورودی را پیدا کنید . اگر بیش از یک جواب وجود داشت می توانید یکی را به دلخواه در خروجی چاپ کنید .

 

محمد مهدی جهان آرا