Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

दिए गए सभी ट्रिपलेट के लिए सबसे छोटे लागत पथ के योग को ढूंढने के लिए C++ प्रोग्राम


मान लीजिए, n शहर हैं और शहरों के बीच m सड़कें हैं। m सड़कें हमें सड़कों के एक ऐरे में दी गई हैं जहां सड़कें {स्रोत, गंतव्य, वजन} प्रारूप में हैं। अब, हम एक ट्रिपलेट (s, t, k) को परिभाषित करते हैं जहां s, t, और k शहर हैं। अब हमें शहर s से शहर t तक पहुंचने के लिए आवश्यक न्यूनतम समय की गणना करनी है। s से t पर जाने के लिए, केवल 1 से k तक के शहरों का दौरा किया जा सकता है। यदि शहर t, s से पहुंच योग्य नहीं है, तो हम 0 वापस करते हैं। हमें सभी ट्रिपलेट (s, t, k) के लिए न्यूनतम समय की गणना करनी है, और उनका योग प्रिंट करना है।

उदाहरण के लिए, यदि इनपुट n = 4, m = 2, edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}} है, तो आउटपुट 63 होगा।

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

मान अनंत से प्रारंभ एक 2D ऐरे dvec परिभाषित करें i := 0 से n-1 तक, करें: dvec[i, i] := 0 i := 0 से m-1 तक, करें: a := edges[i] का पहला मान b := edges[i] का दूसरा मान c := edges[i] का तीसरा मान a और b को 1 से घटाएं dvec[a, b] := c res := 0 k := 0 से n-1 तक, करें: i := 0 से n-1 तक, करें: j := 0 से n-1 तक, करें: dvec[i, j] := dvec[i, j] और dvec[i, k] + dvec[k, j] का न्यूनतम यदि dvec[i, j], अनंत के बराबर नहीं है, तो: res := res + dvec[i, j] print(res)

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; void solve(int n, int m, vector<tuple<int, int, int>> edges){    vector<vector<int>> dvec(n, vector<int>(n, INF));    for(int i = 0; i < n; i++)       dvec[i][i] = 0;    for(int i = 0; i < m; i++) {       int a = get<0> (edges[i]);       int b = get<1> (edges[i]);       int c = get<2> (edges[i]);       a--; b--;       dvec[a][b] = c;    }    int res = 0;    for(int k = 0; k < n; k++) {       for(int i = 0; i < n; i++) {          for(int j = 0; j < n; j++) {             dvec[i][j] = min(dvec[i][j], dvec[i][k]+dvec[k][j]); if(dvec[i][j] != INF) res += dvec[i][j]; } } } cout << res << endl; } int main() { int n = 4, m = 2; vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}; solve(n, m, edges); return 0; }

इनपुट

4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}} 

आउटपुट

63

  1. ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और edges सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक x मान है जो 1 से n के बीच होता है, यह values सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को सुपर वर्टेक्स कहा जाता है

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें

    मान लीजिए हमारे पास एक धनात्मक पूर्णांक L है, जो परफेक्ट बाइनरी ट्री में स्तरों की संख्या दर्शाता है। इस परफेक्ट बाइनरी ट्री में पत्ती नोड्स को 1 से n तक संख्या दी गई है। जहां n पत्ती नोड्स की संख्या है। पैरेंट नोड बच्चों का योग है। हमारा कार्य इस परफेक्ट बाइनरी ट्री के सभी नोड्स का योग प्रिंट करने