المپدیا

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

ابزار کاربر

ابزار سایت


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

کوتاه‌ترین مسیر در گراف

گراف جهت‌دار و وزن‌دار $G$‌ با $n$ راس داده شده است. برنامه‌ای بنویسید که کوتاه‌ترین مسیر جهت‌دار بین هر دو راس آن را (از نظر مجموع وزن یال‌ها) بیابد.

ورودی

در اولین خط فایل ورودی، $n$‌و در $n$ خط بعد از آن، ماتریس مجاورت گراف؛ $A_{n\times n}$ آمده است. درایه‌ی $A_{i,j}$ نماینده‌ی وزن یال بین راس $i$ ام به راس $j$‌ ام گراف است. منفی بودن این مقدار نشان‌گر عدم وجود این یال می‌باشد. تمام درایه‌های این ماتریس را قابل ذخیره‌سازی در یک متغیر از نوع $Integer$ فرض کنید.

خروجی

فایل خروجی باید شامل $n^2$‌ خط باشد و در خط $(i-1)\times n+j$ ام فایل اطلاعات مربوط به کوتاه‌ترین مسیر از راس شماره‌ی $i$‌به راس با شماره‌ی $j$ را بنویسید:

  • در حالت $i=j$ در این سطر فقط یک صفر بنویسید.
  • در صورت عدم وجود چنین مسیری این سطر باید شامل تنها یک عدد منفی باشد.
  • در غیر از دو حالت بالا، در این سطر نخست تعداد یال‌های مسیر و بعد از آن به‌ترتیب شماره‌ی همه‌ی راس‌های مسیر از $i$‌ به $j$ را بنویسید.

همه‌ی عددهای فایل خروجی باید قابل ذخیره‌سازی در متغیری از نوع $Integer$‌ باشند.

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

ورودي نمونه خروجي نمونه
5
0 -1 5 -1 2
1 1 6 -1 -1
-1 3 1 1 4
3 -1 1 0 4
-1 -1 -1 2 0
0
2 1 3 2
3 1 5 4 3
3 1 5 4
1 1 5
1 1 2

ابزار صفحه