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

किसी विशेष शहर से राउंड ट्रिप संभव है या नहीं जाँचने का C++ प्रोग्राम


मान लीजिए n शहर हैं जो m सड़कों से जुड़े हैं। प्रत्येक सड़क एकदिश है और स्रोत शहर से गंतव्य शहर तक पहुँचने में एक विशेष समय लगता है। सड़कों की जानकारी 'roads' सरणी में दी गई है जहाँ प्रत्येक तत्व (स्रोत, गंतव्य, समय) प्रारूप में है। अब एक व्यक्ति एक शहर से दूसरे शहर की यात्रा कर रहा है और यात्रा राउंड-ट्रिप होनी चाहिए। एक यात्रा को राउंड-ट्रिप कहा जाता है जब व्यक्ति किसी विशेष शहर से शुरू करता है, एक या अधिक सड़कों से गुजरता है, और उसी शहर में यात्रा समाप्त करता है। इसलिए प्रत्येक शहर के लिए हमें निर्धारित करना है कि उस विशेष शहर से राउंड-ट्रिप संभव है या नहीं। यदि संभव है, तो राउंड-ट्रिप करने में लगने वाला समय प्रिंट करें अन्यथा -1 प्रिंट करें।

उदाहरण के लिए, यदि इनपुट है n = 4, m = 4, roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}, तो आउटपुट होगा: 26 26 26 26। प्रत्येक शहर से राउंड-ट्रिप करने में 26 समय लगता है।

चरण

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

युग्मों वाला एक 2D सरणी graph(n) परिभाषित करें
i := 0 से m-1 तक:
    x := roads[i] का पहला मान
    y := roads[i] का दूसरा मान
    z := roads[i] का तीसरा मान
    x और y को 1 घटाएँ
    युग्म (y, z) को graph[x] के अंत में डालें
i := 0 से n-1 तक:
    q := एक नई प्राथमिकता कतार
    एक सरणी dst परिभाषित करें
    युग्म (0, i) को q के शीर्ष पर डालें
    जब तक q का आकार शून्येतर:
        युग्म p := q का शीर्ष मान
        q से शीर्ष तत्व हटाएँ
        dt := p का पहला मान
        curr := p का दूसरा मान
        यदि dst[curr] == 0, तो:
            dst[curr] := dt
            लूप से बाहर निकलें
        यदि dst[curr] != -1, तो:
            जारी रखें
        dst[curr] := dt
        graph[curr] में प्रत्येक next तत्व के लिए:
            tp := next का पहला मान
            cst := next का दूसरा मान
            युग्म (dt + cst, tp) को q के शीर्ष पर डालें
यदि dst[i] == 0, तो dst[i] := -1
dst[i] प्रिंट करें

उदाहरण

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

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; const int modval = (int) 1e9 + 7; #define N 100 void solve(int n, int m, vector<tuple<int, int, int>> roads ) {    vector<vector<pair<int, int>>> graph(n);    for(int i = 0; i < m; i++) {       int x, y, z;       tie(x, y, z) = roads[i];       x--; y--;       graph[x].emplace_back(y, z);    }    for(int i = 0; i < n; i++) {       priority_queue<pair<int, int>> q;       vector<int> dst(n, -1);       q.emplace(0, i);       while(q.size()){          pair<int, int> p = q.top();          q.pop();          int curr, dt;          tie(dt, curr) = p;          if(dst[curr] == 0) {             dst[curr] = dt;             break;          }          if(dst[curr] != -1)             continue;         dst[curr] = dt;       for(auto next : graph[curr]){           int tp, cst;           tie(tp, cst) = next;           q.emplace(dt + cst, tp);       }     }     if(dst[i] == 0)    dst[i] = -1;     cout<< dst[i]<< endl;    } } int main() {    int n = 4, m = 4;    vector<tuple<int, int, int>> roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}};    solve(n, m, roads);    return 0; }

इनपुट

4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}

आउटपुट

26 26 26 26
  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++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक भारित, निदेश रहित ग्राफ दिया गया है। ग्राफ का स्कोर ग्राफ में सभी एज भारों का योग है। एज भार ऋणात्मक हो सकते हैं, और यदि उन्हें हटा दिया जाए तो ग्राफ का स्कोर बढ़ जाता है। हमें ग्राफ को संबद्ध रखते हुए एज हटाकर ग्राफ के स्कोर को न्यूनतम करना है। हमें घटाए जा सकन