समस्या
मूल (अंग्रेज़ी) दिखाएँऐसे अविनिर्दिष्ट लिंक चुनें ताकि प्रत्येक शीर्षक (vertex) अन्य सभी शीर्षकों तक पहुँच सके, और कुल लागत न्यूनतम हो। कोई भी लिंक दोनों दिशाओं में इस्तेमाल किया जा सकता है। यदि उपलब्ध लिंक पूरे नेटवर्क को नहीं जोड़ सकते, तो −1 लौटाएँ। आपको चुने गए लिंक लौटाने की आवश्यकता नहीं है।
minimum_network_connection_cost(vertices, links) को लागू करें।
इनपुट
vertices: नेटवर्क में शीर्षकों (vertices) की संख्या।
links: उपलब्ध लिंक [u, v, cost] के रूप में।
आउटपुट
न्यूनतम कुल लागत लौटाएँ, यदि असंभव हो तो −1 लौटाएँ, या एक-शीर्षक नेटवर्क के लिए 0 लौटाएँ।
सीमाएँ
1 ≤ vertices ≤ 100,000। 0…200,000 लिंक; एंडपॉइंट्स 1…vertices में विशिष्ट शीर्षक हैं। लागत 1…1,000,000,000 के बीच है। समान एंडपॉइंट्स के लिए एक से अधिक लिंक (parallel links) की अनुमति है। कुल मान signed 64-bit में समा जाता है।
उदाहरण
इनपुट:
links = [
[1, 2, 4],
[2, 3, 2],
[1, 3, 7]
]
vertices = 3
अपेक्षित आउटपुट:
expected = 6इनपुट:
std::vector<std::vector<long long>> links = {
{1, 2, 4},
{2, 3, 2},
{1, 3, 7}
};
long long vertices = 3;
अपेक्षित आउटपुट:
long long expected = 6;इनपुट:
long[][] links = new long[][] {
new long[] {1, 2, 4},
new long[] {2, 3, 2},
new long[] {1, 3, 7}
};
long vertices = 3;
अपेक्षित आउटपुट:
long expected = 6;व्याख्या
सभी तीन शीर्षकों को जोड़ने के लिए लागत 4 और 2 वाले लिंक चुनें। इनकी कुल लागत 6 है; लागत 7 वाला लिंक आवश्यक नहीं है।
इनपुट:
links = [
[1, 2, 4]
]
vertices = 3
अपेक्षित आउटपुट:
expected = -1इनपुट:
std::vector<std::vector<long long>> links = {
{1, 2, 4}
};
long long vertices = 3;
अपेक्षित आउटपुट:
long long expected = -1;इनपुट:
long[][] links = new long[][] {
new long[] {1, 2, 4}
};
long vertices = 3;
अपेक्षित आउटपुट:
long expected = -1;व्याख्या
शीर्षक 3 का कोई कनेक्शन नहीं है। कोई भी चयन पूरे नेटवर्क को नहीं जोड़ सकता।
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।