إعطاء رسم بياني موجه تم تخصيص بعض الأوزان غير السالبة لحوافه (أطوال). علينا إيجاد رأسين ، أقصر مسار بينهما أكبر طول.
يحتوي السطر الأول على عدد الرؤوس N & le؛ 50. بعد ذلك تأتي مصفوفة التقارب للرسم البياني ، أي صفوف N ، كل منها يحتوي على عدد N. الرقم j في الصف الأول من المصفوفة المجاورة يحدد طول الحافة الممتدة من الرأس من الرتبة إلى الرتبة ي. يمكن أن تأخذ الأطوال أي قيمة من 0 إلى 1000000. ومن المضمون وجود أصفار على القطر الرئيسي للمصفوفة.
& nbsp؛
الإخراج
طباعة رقم واحد & ndash؛ طول المسار المطلوب.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
3
0 7 3
7 0 10
2215 0
|
10
نبسب ؛ |