المپدیا

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

ابزار کاربر

ابزار سایت


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

موش

زیر زمین در دنیای موش‌های کوریک سری میدان وجود دارد. بین هر دو میدانی می‌توان تونل حفر نمود که هزینه‌ی آن به موشی که آن را حفر می‌کند بستگی خواهد داشت. دو تا موش که از قضا خیلی با هم رفیقند، باید هر روز صبح از خونه‌هاشون برن به محل کارشون. در ابتدای روز هیچ تونلی وجود ندارد ولی هر تونلی که موش‌ها حفر کنند، تا آخر شب وجود خواهد داشت.

برنامه‌ای بنویسید که با دریافت اطلاعات خانه‌ی موش‌ها و محل کارشون و نیز هزینه‌ی حفر تونل بین دو میدان برای هر موش، کم‌ترین هزینه‌ی لازم برای رسیدن دو موش به محل کارشون را حساب کنید.

ورودی

در سطر اول $n$‌که تعداد میدان‌هاست، داده شده. در سطر بعدی شماره‌ی میدان خانه و محل کار موش اول آمده و در $n-1$‌سطر بعد، نیمه‌ی پایین ماتریس مجاورت او می‌آید. عدد $j$ام در سطر $i$‌ام این ماتریس مجاورت یک موش نشان می‌دهد که او برای حفر تونلی بین میدان $i$ و $j$‌ چه هزینه‌ای باید صرف کند؛ اگر این عدد صفر باشد، یعنی این موش نمی‌تواند بین این دو میدان تونل حفر کند. سپس میدان شروع و پایان و نیمه‌ی پایین ماتریس موش دوم می‌آید.($1\leq n \leq 200$)

خروجی

در سطر اول کم‌ترین هزینه را بنویسید و در سطرهای بعدی تونل‌های حفر شده را به ترتیب زمانی بنویسید. برای هر تونل به ترتیب سه عدد $v،u$‌و $m$‌بنویسید که نشان می‌دهد موش شماره‌ی $m$ از میدان $u$ به میدان $v$ تونل حفر می‌کند.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4
1 3
5
35 4
0 40 40
1 4
10
40 40
30 11 36
20
1 2 1
2 4 2
2 3 1

ابزار صفحه