گراف جهتدار و وزندار $G$ با $n$ راس داده شده است. برنامهای بنویسید که کوتاهترین مسیر جهتدار بین هر دو راس آن را (از نظر مجموع وزن یالها) بیابد.
در اولین خط فایل ورودی، $n$و در $n$ خط بعد از آن، ماتریس مجاورت گراف؛ $A_{n\times n}$ آمده است. درایهی $A_{i,j}$ نمایندهی وزن یال بین راس $i$ ام به راس $j$ ام گراف است. منفی بودن این مقدار نشانگر عدم وجود این یال میباشد. تمام درایههای این ماتریس را قابل ذخیرهسازی در یک متغیر از نوع $Integer$ فرض کنید.
فایل خروجی باید شامل $n^2$ خط باشد و در خط $(i-1)\times n+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 |