Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

مسیر رنگی

یک گراف n راسی داریم که به هر یال آن یک رنگ نسبت داده‌ایم. حال می‌خواهیم یک مسیر از راس s به راس t پیدا کنیم کم‌ترین مقدار تغییر رنگ را داشته باشد.

مقدار تغییر رنگ در مسیر s=k0,k1,k2,...,k3=t برابر است با تعداد 0<j<r هایی که رنگ یال (kj1,kj) و یال (kj,kj+1) متفاوت باشد.

ورودی

در خط اول فایل ورودی به ترتیب اعداد n و s و t آمده‌اند. سپس نیمه‌ی پایین ماتریس مجاورت گراف آمده است. می‌دانیم n100 و تعداد یال‌های گراف کم‌تر یا مساوی ۱۰۰۰ است. اعداد ماتریس تماما نامنفی هستند و نشان‌دهنده‌ی رنگ یال‌های گراف می‌باشند. (عدد ۰ یعنی یالی وجود ندارد)

خروجی

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

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

ورودي نمونه خروجي نمونه
7 1 6
2
1 0
0 0 2
0 0 0 1
0 0 0 0 1
0 1 0 0 3 0
2

ابزار صفحه