طولانی ترین راه
Problem
یک نمودار جهت دار داده می شود که به لبه های آن وزن های غیر منفی (طول) اختصاص داده شده است. ما باید دو راس را پیدا کنیم که کوتاهترین مسیر بین آنها بیشترین طول را دارد.
ورودی
خط اول شامل تعداد رئوس N ≤50 است. بعد ماتریس مجاورت نمودار می آید، یعنی N ردیف که هر کدام حاوی N عدد است. عدد j در ردیف i ام ماتریس مجاورت طول یال منتهی به راس i به j ام را مشخص می کند. طول ها می توانند هر مقداری از 0 تا 1000000 داشته باشند. وجود صفر در مورب اصلی ماتریس تضمین شده است.
خروجی
چاپ یک عدد – طول مسیر مورد نظر.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|