المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:عملی:سوال ۶

Flu

بعد از سفر تیم ملی المپیاد کامپیوتر به کشور بلغارستان خبری به آن‌ها رسید که ‎$K$‎ تا از مبتلایان به آنفولانزای خوکی در شهر پلاودیو (همان شهری که المپیاد امسال در آن برگزار شد و تیم المپیاد کامپیوتر در آن هستند) از قرنطینه فرار کرده‌اند و هدفشان مبتلا کردن بقیه مردم به آنفولانزای خوکی است. بعد از شنیدن این خبر، اعضای تیم و همراهان آن‌ها تصمیم گرفتند در اسرع وقت خود را به فرودگاه برسانند و به میهن عزیزمان بازگردند. نقشه شهر پلاودیو به صورت یک گراف ساده با ‎$N$‎ رأس و ‎$E$‎ یال داده شده است. رئوس از ‎۱‎ تا ‎$N$‎ شماره‌گذاری شده‌اند (وزن همه یال‌ها یک است و یال‌ها بدون جهت هستند). تیم المپیاد کامپیوتر در هر ساعت می تواند یک یال را بپیماید و به یکی از رئوس مجاور برود یا در رأسی که در آن بود بماند (توجه کنید که اعضای تیم همیشه با هم هستند). هر بیمار بعلت بیماری در هر ‎$T$‎ ساعت می‌تواند یک یال را بپیماید و به یکی از رئوس مجاور برود یا در همان رأس بماند. خوشبختانه سازمان مبارزه با آنفولانزای خوکی محل فرار هر یک از بیماران را اعلام کرده است و تیم المپیاد هم در همان لحظه‌ای که بیماران شروع به حرکت می‌کنند، شروع به حرکت می‌کنند.

ما می‌خواهیم تیم از مسیری به فرودگاه برود که احتمال وارد شدن به رأسی، همزمان با ورود یک بیمار به آن رأس در طول راه، وجود نداشته باشد. ما حتی می‌خواهیم ممکن نباشد تیم در رأس فرودگاه با یک بیمار مواجه شود. در زمان شروع به حرکت کردن، تیم المپیاد کامپیوتر ایران در رأس ‎۱‎ قرار دارد و بیمار ‎$i$‎ام در رأس ‎$P_i$‎ قرار دارد. فرودگاه نیز در رأس ‎$N$‎ام قرار دارد. شما باید در صورت وجود مسیری برای نجات تیم المپیاد، کوتاه‌ترین مسیر را پیدا کنید.

ورودی

  • در سطر اول ورودی، چهار عدد ‎$N$ (تعداد رئوس نقشه)، ‎$E$ (تعداد یال‌های نقشه)، ‎$K$ (تعداد بیماران) و ‎$T$ (تعداد ساعاتی که طول می‌کشد تا یک بیمار یک یال را بپیماید) به ترتیب داده شده است.
  • در سطر دوم ‎$K$‎ عدد آمده است که شماره رئوسی هستند که بیماران در شروع حرکت در آن‌ها قرار دارند.
  • در ‎$E$‎ سطر بعد، در هر سطر دو عدد آمده است که دو سر یک یال را نشان می‌دهند.
  • ‎$2 \le N \le 50000$‎.
  • ‎$0 \le K \le 50000$‎.
  • ‎$0 \le E \le 100000$‎.
  • ‎$1 \le T \le 10^6$‎

خروجی

  • اگر مسیری برای نجات تیم وجود داشت در سطر اول طول کوتاه‌ترین مسیر و در سطر دوم رئوس یکی از کوتاه‌ترین مسیرها را (شامل رئوس ‎۱‎ و ‎$N$) به ترتیب بنویسید.
  • در صورتی که مسیر وجود نداشت در یک سطر بنویسیدimpossible ‎.
  • توجه: برنامه‌ی شما برای گرفتن نمره‌ی تست‌هایی که جواب آن‌ها ‎impossible‎ است، می‌بایست حداقل به یکی از تست‌هایی که جواب آن‌ها ‎impossible‎ نیست پاسخ صحیح بدهد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
8 11 3 2‎
2 4 6‎
1 2‎
1 3‎
2 4‎
3 4‎
4 6‎
6 5‎
3 5
‎6 7‎
3 7‎
8 3‎
7 8
3‎
1 3 8
7 8 1 2‎
5‎
1 2‎
1 3‎
2 4‎
3 6‎
4 5‎
5 6‎
4 7
‎6 7
impossible

‎‎ ‎‎


ابزار صفحه