ای سی ام کار تازه وارد

لینک سوال

مفهوم سوال

شهری داریم که از یه سری خیابان و یه سری تقاطع تشکیل شده .

تو هر تقاطع یه چراغ نصب شده که با زمان بندی مشخص آبی و قرمز میشه .

از یک خیابان میشه گذر کرد اگر و تنها اگر چراغ دوسر اون زمان شروع حرکت هم رنگ باشند .

سوال از ما می خواد کوتاه ترین مسیر از نقطه ای به نقطه دیگه رو بدست بیارم .

به عنوان ورودی به ما وضعیت اولیه چراغ ها ( رنگ فعلی ، زمان باقیمونده از دوره فعلی و دوره زمانی هر رنگ از این چراغ ) ، وضعیت خیابان ها ، نقطه شروع و انتهای مسیر رو میده .

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

حل

برای حل از الگوریتم Dijkstra استفاده خواهیم کرد .

گراف متناظر با مساله رو می سازیم . زمان ساخت گراف توجهی به رنگ دو سر نداریم .

حالا کافیه با شروع از نقطه ابتدا Dijkstra بزنیم .

تو هر state از کار ، به ازای هر گرۀ همسایه با این گره ، اولین زمانی بعد از زمان رسیدن به این گره رو بدست میاریم که چراغ هر دو طرف همرنگ باشه ؛ گرۀ همسایه با این زمان می تونه update بشه .

مثلا update کردن همسایه های یه گره می تونه اینجوری باشه .

if( dis[ adj[u][i].u ] > GetTime( adj[u][i].u , CurrentTime ) + adj[u][i].cost )
    update( adj[u][i].u , GetTime( adj[u][i].u , CurrentTime ) + adj[u][i].cost );

چون دوره زمانی چراغ ها حداکثر 100 ثانیه است ، می تونیم وضعیت رنگ دو سر هر یال رو تو یه بازه 100 ثانیه ای در نظر بگیریم .

برای بدست آوردن رنگ یه چراغ تابعی می نویسیم که شماره گره و یه زمان دلخواه رو از ما میگیره و رنگ گره رو تو اون زمان به ما میده .

برای بدست آوردن مسیر هم می تونیم برای هر گره آخرین گره ای که update کردش رو نگه داریم .

با شروع از نقطه انتهایی مسیر ، می تونیم پله پله به عقب برگردیم و مسیر رو بسازیم .

پی نوشت : اگر با Dijkstra آشنایی ندارید این مطلب رو بخونید .