Processing math: 57%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

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

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

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

ورودی

  • در خط اول ورودی چهار عدد n و m و t و k آمده‌است که به ترتیب تعداد شهرها، تعداد جاده‌ها، تعداد طلب‌کارها و حداکثر مسافتی که طلب‌کارها حاضرند طی کنند را نشان می‌دهد.
  • در m خط بعد در هر خط ۳ عدد ui و vi و wi آمده است که وجود یک جاده دو طرفه به طول wi از شهر ui به شهر vi را نشان می دهد. (بین هر دو شهر حداکثر یک جاده وجود دارد و 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

ابزار صفحه