رحلة ملكية
Problem
رغب جلالة الملك بوبي الثاني في السفر حول منطقته. في الوقت نفسه ، يحتوي المسار على الرغبات التالية:
1) يجب أن يستغرق الطريق أقل وقت ممكن (الوقت الملكي & ndash ؛ شيء ثمين للغاية ويجب حمايته) ؛
2) يجب أن يشمل المسار جميع المستوطنات مرة واحدة بالضبط (إذا فات الملك تسوية ، فسيغضب سكانها بسبب عدم الاهتمام الملكي ويتوقفون عن دفع الضرائب ؛ إذا زار الملك مستوطنة أكثر من مرة ، فإن سكان الباقين بنود المستوطنات ستكون أيضا غاضبة)
3) يجب أن يبدأ المسار وينتهي في عاصمة الولاية (بعد أن سافر حول ممتلكاته ، يجب على الملك أن يبدأ العمل على الفور). يتم تضمين العاصمة في المسار مرتين بالضبط: كنقطة انطلاق وكوجهة ، لا يمكن أن تكون مستوطنة وسيطة للطريق.
اكتب برنامجًا يستخدم خارطة طريق المملكة للعثور على مثل هذا الطريق أو يقرر أنه من المستحيل تلبية جميع المتطلبات.
إدخال
أدخل أولاً الرقم N (طبيعي ، لا يتجاوز 10) & ndash؛ عدد المستوطنات في المملكة. ثم يتبع سطور N من أرقام N في كل & ndash؛ وقت السفر بين المستوطنات (الوقت - عدد صحيح غير سالب ، لا يتجاوز 500 ؛ إذا كان الوقت = 0 ، فهذا يعني أنه لا توجد طريقة بين بعض المستوطنات). المستوطنة رقم 1 هي عاصمة الدولة.
بصمة
اطبع أقل وقت إجمالي سيقضيه جلالة الملك في التفاف حول نطاقاته ، أو الرقم -1 إذا كان من المستحيل إنشاء طريق بالخصائص المحددة.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85 نبسب ؛
85 0 نبسب؛ |
170 |