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

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

• سوال بعد
• سوال قبل