Processing math: 60%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۴۸

BFS in Complement Graph

فرض کنید گرافی n راسی تهی دارید. در هر مرحله یک زیرگراف k راسی از گراف را می‌گیریم و آنرا کامل می‌کنیم. پس از انجام تمام مراحل، فاصله‌ی راس 1 تا n را به دست آورید.

ورودی

  • به ترتیب n، k و m که m تعداد زیرگراف‌های انتخابی‌ست.
  • در m خط بعد در هر خط k‌ عدد آمده است که هر‌کدام نشان‌دهنده‌ی راس‌های یک زیرگراف است.
  • 1 \leq n \leq 10^6
  • 1 \leq m, k \leq 1000

خروجی

  • کم‌ترین فاصله‌ی راس 1 از n را به‌دست آورید.
  • اگر مسیری وجود ندارد -1 چاپ کنید.

محدودیت‌ها

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

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

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

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه