المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۴:عملی مقدماتی اول:سوال ۳

سوال ۳

خانم دکتر، خانم نسبتن ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با $n$ شهر زندگی می کند که شهرهایش با $m$ جاده دو طرفه به هم متصل هستند. هر جاده نیز طول مشخصی دارد.

اخیرن خانم دکتر به علت خرید های زیادش بدهی بالا آورده و $t$ چک دست طلب‌کارهایش دارد. طلب کار $i$ام در شهر $a_i$ زندگی‌ می‌کند و چک این طلب‌کار در روز $i$ام برگشت می خورد. هر طلب کار بعد از برگشت خوردن چکش می خواهد خانم دکتر را پیدا کند و او را به زندان بیندازد. ولی از آن جایی که طلب‌کارها آدم های تنبلی هستند، در صورتی به دنبال خانم دکتر می‌روند که فاصله شهرشان تا شهر خانم دکتر کمتر از $k$ باشد.

حال آقای مهندس، همسر مهربان خانم دکتر، در هر یک از $t$ روز می خواهد بداند که خانم دکتر را به چند شهر می‌تواند فراری دهد که از دست طلب‌کارها در امان باشد. به او کمک کنید!

ورودی

  • در خط اول ورودی چهار عدد $n$ و $m$ و $t$ و $k$ آمده‌است که به ترتیب تعداد شهرها، تعداد جاده‌ها، تعداد طلب‌کارها و حداکثر مسافتی که طلب‌کارها حاضرند طی کنند را نشان می‌دهد.
  • در $m$ خط بعد در هر خط ۳ عدد $u_i$ و $v_i$ و $w_i$ آمده است که وجود یک جاده دو طرفه به طول $w_i$ از شهر $u_i$ به شهر $v_i$ را نشان می دهد. (بین هر دو شهر حداکثر یک جاده وجود دارد و $u_i \neq v_i$)
  • در $i$امین خط از $t$ خط بعد یک عدد $a_i$ آمده‌است که نشان دهنده شهر محل زندگی طلب‌کار $i$ام است.
  • $1 \leq n \leq 5 * 10^4, 0 \leq m \leq 8 * 10^4$
  • $0 \leq t \leq n$
  • $1 \leq k \leq 100$
  • $1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 100$
  • $1 \leq a_i \leq n$

خروجی

در $t$ خط خروجی در خط $i$ام تعداد شهر هایی که خانم دکتر در روز $i$ در امان است را چاپ کنید.

زیرمسئله‌ها

  • زیر مسئله اول (۳۰ نمره): $1 \leq n \leq 400$
  • زیر مسئله دوم (۷۰ نمره - بدون فیدبک):‌ بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
7 6 3 3
3 4 1
3 5 1
4 7 1
5 1 1
3 6 1
6 2 2
4
3
6
2
1
0
1 0 1 1
1
0

ابزار صفحه