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

گراف جهت‌دار و وزن‌دار $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$‌ باشند.

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

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|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|

</WRAP>

  * [[سوال ۱۶|سوال بعد]]
  * [[سوال ۱۴|سوال قبل]]