في رسم بياني غير موجه ، تريد معرفة طول أقصر مسار بين رأسين.
الإدخال: & nbsp؛
- يحتوي السطر الأول من الإدخال على الرقم
N - عدد الرؤوس في الرسم البياني (
\ (1 & lt؛ = N & lt؛ = 100 \) ) ؛
- & nbsp ؛ بعد ذلك ، تتم كتابة مصفوفة التقارب من سطر جديد ( 0 يشير إلى عدم وجود حافة ، 1 - وجود حافة) ؛
- & nbsp ؛ السطر الأخير & nbsp ؛ يحتوي على عدد رأسين - البداية والنهاية.
& nbsp؛
الإخراج: & nbsp؛ اطبع طول أقصر مسار. إذا كان المسار غير موجود ، فقم بطباعة رقم واحد -1 .
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
|
3 |