सुरक्षित संयोजन
Problem
हाल ही में वायरटैपिंग की खबरों के आलोक में, दो कट्टर इंटरनेट दिग्गज उरागनिया Laim.UR और "ज़ेंडा" ने एक दूसरे के डेटा केंद्रों के बीच एक सुरक्षित संचार चैनल स्थापित करने के लिए एक समझौते पर हस्ताक्षर करने का निर्णय लिया। उरगनिया में n शहर हैं, लेकिन, दुर्भाग्य से, किसी भी शहर में दोनों दिग्गजों के डेटा सेंटर नहीं हैं। इसलिए एक सुरक्षित चैनल बनाने के लिए लंबी दूरी की संचार लाइनें बिछानी होंगी।
कंपनियों के विशेषज्ञों ने शहरों के एम जोड़े की पहचान की है जिन्हें एक संचार चैनल सेगमेंट बिछाकर जोड़ा जा सकता है और इनमें से प्रत्येक जोड़े के लिए ऐसा सेगमेंट बनाने की लागत का अनुमान लगाया है।
परिणामी चैनल में कई खंड शामिल हो सकते हैं। यह उन शहरों में से एक में शुरू होना चाहिए जहां पहली कंपनी का डाटा सेंटर स्थित है, यह मध्यवर्ती शहरों से गुजर सकता है और उस शहर में समाप्त होना चाहिए जहां दूसरी कंपनी का डाटा सेंटर स्थित है।
अब दो कंपनियों के डेटा केंद्रों को जोड़ने वाले सुरक्षित चैनल की न्यूनतम लागत का निर्धारण करना आवश्यक है।
इनपुट:
पहली पंक्ति में पूर्णांक n और m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 105 ) — शहरों की संख्या और शहरों के जोड़े की संख्या जो एक लिंक सेगमेंट से जुड़ सकते हैं। दूसरी पंक्ति में n पूर्णांक ai (0 ≤ ai ≤ 2) है। अगर ai = 0, तो i-th शहर में किसी भी दिग्गज का कोई डेटा सेंटर नहीं है। यदि ai = 1, तो "Laim.UR" डेटा केंद्र i-वें शहर में स्थित है, और यदि ai = 2, तो "Xenda" डेटा केंद्र i-वें शहर में स्थित है। वें शहर; यह गारंटी है कि इन संख्याओं में कम से कम एक एक और एक दो है। अगली m पंक्तियों में से प्रत्येक में तीन पूर्णांक हैं — si , ti और ci , जिसका अर्थ है कि शहर si और ti (1 ≤ si , ti ≤ n, si != ti< /sub>) को लागत ci (1 ≤ ci ≤ 105 ) के एक लिंक खंड से जोड़ा जा सकता है। शहरों की प्रत्येक जोड़ी को अधिकतम एक चैनल सेगमेंट से जोड़ा जा सकता है।
आउटपुट:
यदि विभिन्न इंटरनेट दिग्गजों के दो डेटा केंद्रों को एक सुरक्षित संचार चैनल से जोड़ना संभव है, तो आउटपुट फ़ाइल में तीन नंबर प्रिंट करें: x, y और d, जिसका अर्थ है कि शहरों x और y के बीच एक संचार चैनल स्थापित करना संभव है डी की कुल लागत। शहर x में एक डाटा सेंटर "Laim.UR" होना चाहिए, शहर में y — डाटा सेंटर «Xenda». यदि कई इष्टतम उत्तर हैं, तो किसी एक को प्रिंट करें। यदि आवश्यक चैनल बनाना असंभव है, तो −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.