اتصال آمن
Problem
في ضوء أخبار التنصت الأخيرة ، عملاق الإنترنت المتشددان Uragania Laim.UR و "Xenda" قررت التوقيع على اتفاقية إنشاء قناة اتصال آمنة بين مراكز البيانات كل منهما. توجد مدن ن في أوراجانيا ، ولكن للأسف لا توجد مراكز بيانات لكلا العملاقين في أي مدينة. لذلك ، لتشكيل قناة آمنة ، يجب وضع خطوط اتصال بعيدة المدى.
حدد المتخصصون في الشركات عددًا من الأزواج من المدن التي يمكن ربطها عن طريق وضع قطاع قناة اتصال وقدر تكلفة إنشاء مثل هذا القطاع لكل من هذه الأزواج.
قد تتكون القناة الناتجة من عدة مقاطع. يجب أن يبدأ في إحدى المدن التي يوجد بها مركز بيانات الشركة الأولى ، ويمكن أن يمر عبر مدن وسيطة ويجب أن ينتهي في المدينة التي يوجد بها مركز بيانات الشركة الثانية.
من الضروري الآن تحديد التكلفة الدنيا لقناة آمنة تربط مركزي بيانات شركتين.
الإدخال:
يحتوي السطر الأول على أعداد صحيحة n و m (2 & le؛ n & le؛ 5000، 1 & le؛ m & le؛ 10 5 ) & mdash؛ عدد المدن وعدد أزواج المدن التي يمكن توصيلها بواسطة جزء ارتباط. يحتوي السطر الثاني على n أعداد صحيحة ai (0 & le؛ a i & le؛ 2). إذا كان i = 0 ، فلا يوجد مركز بيانات لأي من العمالقة في المدينة الأولى. إذا كان ai = 1 ، فإن مركز بيانات "Laim.UR" يقع في المدينة الأولى ، وإذا كان i = 2 ، فإن مركز بيانات "Xenda" يقع في i- المدينة ال من المؤكد أن من بين هذه الأرقام يوجد واحد وواحد على الأقل. يحتوي كل سطر من السطور التالية على ثلاثة أعداد صحيحة و [مدش] ؛ s i و t i و c i ، مما يعني أن المدن s i و t i (1 & le؛ s i ، t i & le؛ n، s i & nbsp؛! = t i < / sub>) بواسطة شريحة ارتباط بتكلفة ci (1 & le؛ c i & le؛ 10 5 ). يمكن ربط كل زوج من المدن من خلال قطاع قناة واحد على الأكثر.
الإخراج:
إذا كان من الممكن توصيل مركزي بيانات لعمالقة إنترنت مختلفين بقناة اتصال آمنة ، فقم بطباعة ثلاثة أرقام في ملف الإخراج: x و y و d ، مما يعني أنه من الممكن إنشاء قناة اتصال بين المدن x و y مع بتكلفة إجمالية د. في المدينة x يجب أن يكون هناك مركز بيانات "Laim.UR" ، في المدينة y & [مدش]؛ مركز البيانات "زندا". إذا كان هناك العديد من الإجابات المثلى ، فقم بطباعة أي منها. إذا كان من المستحيل رسم القناة المطلوبة ، اطبع & ناقص ؛ 1.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1
| 3 4 5 |
| 2 |
4 2
1 0 0 2
1 3 3
2 4 2
| -1 |
شرح
في المثال الأول ، من الأفضل بناء قناة اتصال من جزأين: 3 & ناقص؛ 2 و 2. 4.