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

समस्या विवरण

हमारे पास दो सूचियाँ costs_from और costs_to हैं जिनका आकार समान है। प्रत्येक इंडेक्स i एक शहर को दर्शाता है। शहर i से शहर j तक एक एकतरफा सड़क बनाने की लागत costs_from[i] + costs_to[j] होती है। हमारे पास पहले से मौजूद सड़कों की एक सूची edges भी है, जहाँ प्रत्येक एज [x, y] शहर x से शहर y तक एक एकतरफा सड़क को दर्शाती है। हमें शहर 0 से किसी भी अन्य शहर तक पहुँचने के लिए आवश्यक नई सड़कों के निर्माण की न्यूनतम लागत ज्ञात करनी है।

उदाहरण

इनपुट: costs_from = [6, 2, 2, 12], costs_to = [2, 2, 3, 2], edges = [[0, 3]]

आउटपुट: 13

व्याख्या: हम शहर 0 से शहर 2 तक 9 की लागत (6+3) में जा सकते हैं। फिर शहर 2 से शहर 1 तक 4 की लागत (2+2) में जा सकते हैं। शहर 0 से शहर 3 तक सड़क पहले से मौजूद है। कुल लागत = 9 + 4 = 13।

एल्गोरिदम

1. n := costs_from का आकार
2. ret := 0 प्रारंभ करें
3. दो मैप edges और redges परिभाषित करें (आगे और पीछे के एज के लिए)
4. दिए गए g में प्रत्येक एज के लिए:
   • edges[it[0]] में it[1] जोड़ें
   • redges[it[1]] में it[0] जोड़ें
5. from_cost := INF सेट करें
6. दो सेट visited और reachable परिभाषित करें
7. DFS फंक्शन परिभाषित करें जो टोपोलॉजिकल क्रम (po) बनाता है
8. दूसरा DFS फंक्शन dfs2 परिभाषित करें जो पहुँच योग्य घटकों की जाँच करता है
9. BFS का उपयोग करके शहर 0 से पहुँच योग्य सभी शहरों को चिह्नित करें और from_cost को अपडेट करें
10. global_min := costs_from का न्यूनतम तत्व
11. ret := ret + from_cost - global_min
12. सभी अनदेखे नोड्स के लिए टोपोलॉजिकल क्रम (po) की गणना करें
13. po को उलट दें
14. po में प्रत्येक नोड के लिए:
    • यदि पहले से पहुँच योग्य है, तो छोड़ दें
    • visited साफ़ करें और dfs2 चलाएँ
    • यदि initial सत्य है, तो visited में न्यूनतम costs_to खोजें और ret में जोड़ें
15. ret वापस करें

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<int>& costs_from, vector<int>& costs_to, vector<vector<int>>& g) {
        int n = costs_from.size();
        int ret = 0;
        unordered_map<int, vector<int>> edges, redges;
        
        for (auto& it : g) {
            edges[it[0]].push_back(it[1]);
            redges[it[1]].push_back(it[0]);
        }
        
        int from_cost = INT_MAX;
        unordered_set<int> visited, reachable;
        queue<int> q;
        
        reachable.insert(0);
        q.push(0);
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            for (int i : edges[node]) {
                if (!reachable.count(i)) {
                    reachable.insert(i);
                    q.push(i);
                }
            }
            from_cost = min(from_cost, costs_from[node]);
        }
        
        int global_min = *min_element(costs_from.begin(), costs_from.end());
        ret += from_cost - global_min;
        
        vector<int> po;
        function<void(int)> dfs = [&](int i) {
            if (!visited.count(i) && !reachable.count(i)) {
                visited.insert(i);
                for (int j : edges[i]) dfs(j);
                po.push_back(i);
            }
        };
        
        for (int i = 0; i < n; i++) dfs(i);
        reverse(po.begin(), po.end());
        
        function<bool(int)> dfs2 = [&](int i) {
            if (visited.count(i)) return true;
            if (reachable.count(i)) return false;
            visited.insert(i);
            reachable.insert(i);
            bool ret = true;
            for (int j : redges[i]) ret &= dfs2(j);
            return ret;
        };
        
        for (int i : po) {
            if (reachable.count(i)) continue;
            visited.clear();
            bool initial = dfs2(i);
            if (initial) {
                int best = INT_MAX;
                for (int j : visited) best = min(best, costs_to[j]);
                ret += global_min + best;
            }
        }
        
        return ret;
    }
};

int main() {
    vector<int> costs_from = {6, 2, 2, 12};
    vector<int> costs_to = {2, 2, 3, 2};
    vector<vector<int>> edges = {{0, 3}};
    cout << (new Solution())->solve(costs_from, costs_to, edges);
    return 0;
}

आउटपुट

13