يتم إعطاؤك رسم بياني مرجح موجه. ابحث عن أقصر مسار من رأس معين إلى آخر.
يحتوي السطر الأول على ثلاثة أرقام: N و S و F (1 & le؛ N & le؛ 100، 1 & le؛ S، F & le؛ N) ، حيث N & ndash؛ عدد رؤوس الرسم البياني ، S & ndash ؛ الرأس الأولي و F & ndash؛ أخير. في السطور N التالية ، أدخل أرقام N لكل منها ، بما لا يتجاوز 100 ، & ndash؛ مصفوفة تجاور الرسم البياني ، حيث يعني -1 عدم وجود حافة بين الرؤوس وأي رقم غير سالب & ndash؛ وجود حافة وزن معين. الأصفار مكتوبة على القطر الرئيسي للمصفوفة.
& nbsp؛
الإخراج
مطلوب عرض تسلسلي جميع رؤوس واحد (أي) من أقصر المسارات ، أو رقم واحد -1 إذا لم يكن هناك مسار بين الرؤوس المحددة. & nbsp؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |