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

ट्रेन से स्रोत से गंतव्य स्टेशन तक पहुँचने के लिए न्यूनतम समय ज्ञात करने का C++ प्रोग्राम


मान लीजिए n स्टेशन m पटरियों से जुड़े हैं। स्टेशन 1 से n तक नामित हैं। पटरियाँ द्विदिश हैं और हमें स्टेशन src से स्टेशन dst तक पहुँचना है। i-वें रेलमार्ग के स्रोत और गंतव्य स्टेशन 'roads' सरणी में दिए गए हैं जहाँ roads[i] का प्रारूप {station1, station2} है। j-वें स्टेशन से, समय kj के गुणकों पर सभी जुड़े स्टेशनों के लिए ट्रेन प्रस्थान करती है और प्रत्येक ट्रेन को गंतव्य तक पहुँचने में tj समय लगता है। ये मान 'departure' सरणी में दिए गए हैं जहाँ प्रत्येक तत्व {tj, kj} प्रारूप में है। हमें src से dst तक पहुँचने में लगने वाले न्यूनतम संभावित समय की गणना करनी है। हम कई ट्रेनें बदल सकते हैं और ट्रेन बदलने में लगने वाला समय नगण्य है।

उदाहरण के लिए, यदि इनपुट है n = 4, m = 3, src = 1, dst = 4, roads = {{1, 2}, {2, 4}, {3, 4}}, departure = {{2, 1}, {3, 5}, {7, 6}}, तो आउटपुट 8 होगा।

स्टेशन 1 से, हम समय 0 पर स्टेशन 2 के लिए ट्रेन लेते हैं। स्टेशन 2 पहुँचने में 2 समय लगता है। स्टेशन 2 से, हम समय 5 पर स्टेशन 4 के लिए ट्रेन लेते हैं। स्टेशन 4 पहुँचने में 3 समय लगता है। कुल समय (5 + 3) = 8।

चरण

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

src := src - 1
dst := dst - 1
टपल्स वाला एक नया सरणी graph[n] परिभाषित करें
i := 0 से m-1 तक:
    a := roads[i] का पहला मान - 1
    b := roads[i] का दूसरा मान - 1
    t := departure[i] का पहला मान
    k := departure[i] का दूसरा मान
    टपल (b, t, k) को graph[a] के अंत में डालें
    टपल (a, t, k) को graph[b] के अंत में डालें
आकार n का सरणी dp परिभाषित करें जिसे -9999 से आरंभ किया गया हो
युग्मों वाली एक प्राथमिकता कतार priq परिभाषित करें
dp[src] := 0
priq में युग्म (-dp[src], src) डालें
जब तक priq खाली न हो:
    टपल (w, a) := priq का सबसे बड़ा मान
    priq से शीर्ष तत्व हटाएँ
    यदि a == dst, तो:
        -w लौटाएँ
    यदि w < dp[a], तो:
        अगली पुनरावृत्ति पर जाएँ
    graph[a] में प्रत्येक v के लिए:
        टपल (b, t, k) बनाएँ
        weight := (w - k + 1) / k * k - t
        यदि weight > dp[b], तो:
            dp[b] := weight
            priq में युग्म (weight, b) डालें
-1 लौटाएँ

उदाहरण

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

#include <bits/stdc++.h> using namespace std; int solve(int n, int m, int src, int dst, vector<pair<int, int>> roads, vector<pair<int, int>> departure){    src -= 1;    dst -= 1;    vector<tuple<int, int, int>> graph[n];    int a, b;    int t, k;    for(int i = 0; i < m; i++){       a = roads[i].first - 1;       b = roads[i].second - 1;       t = departure[i].first;       k = departure[i].second;       graph[a].emplace_back(b, t, k);       graph[b].emplace_back(a, t, k);    }    vector<int> dp(n, -9999);    priority_queue<pair<int, int>> priq;    dp[src] = 0;    priq.push(make_pair(-dp[src], src));    int w;    while(not priq.empty()){       tie(w, a) = priq.top();       priq.pop(); if(a == dst){          return -w;       }       if(w < dp[a])          continue;       for(auto &v: graph[a]){          tie(b, t, k) = v;          int weight = (w - k + 1) / k * k - t; if(weight > dp[b]){ dp[b] = weight; priq.push(make_pair(weight, b)); } } } return -1; } int main() { int n = 4, m = 3, src = 1, dst = 4; vector<pair<int, int>> roads = {{1, 2}, {2, 4}, {3, 4}}, departure = {{2, 1}, {3, 5}, {7, 6}}; cout<< solve(n, m, src, dst, roads, departure); return 0; }

इनपुट

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

आउटपुट

8
  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 एज वाला एक भारित, निदेश रहित ग्राफ दिया गया है। ग्राफ का स्कोर ग्राफ में सभी एज भारों का योग है। एज भार ऋणात्मक हो सकते हैं, और यदि उन्हें हटा दिया जाए तो ग्राफ का स्कोर बढ़ जाता है। हमें ग्राफ को संबद्ध रखते हुए एज हटाकर ग्राफ के स्कोर को न्यूनतम करना है। हमें घटाए जा सकन