सी++ में पहले शहर से किसी भी शहर तक पहुंचने के लिए हमें न्यूनतम सड़कों का पता लगाने का कार्यक्रम

मान लीजिए कि हमारे पास एक ही आकार की दो सूचियां cost_from और cost_to हैं जहां प्रत्येक अनुक्रमणिका i एक शहर का प्रतिनिधित्व करती है। यह शहर i से j तक एकतरफा सड़क बना रहा है और उनकी लागत लागत_ से [i] + लागत_ से [j] है। हमारे पास किनारों की एक सूची भी है जहां प्रत्येक किनारे में [x, y] इंगित करता है कि शहर x से y तक पहले से ही एकतरफा सड़क है। यदि हम 0 शहर से किसी भी शहर में जाना चाहते हैं, तो हमें आवश्यक सड़कों के निर्माण के लिए न्यूनतम लागत का पता लगाना होगा।

इसलिए, यदि इनपुट लागत_ से =[6, 2, 2, 12] लागत_ से =[2, 2, 3, 2] किनारों =[[0, 3]] जैसा है, तो आउटपुट 13 होगा, जैसा कि हम जा सकते हैं 9 की लागत के लिए 0 से 2 तक। उसके बाद, हम 4 की लागत के लिए 2 से 1 तक जा सकते हैं। और हमारे पास 0 से 3 तक जाने का रास्ता पहले से ही है। तो कुल 9 + 4 =13 है। पी>

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

• n :=लागतों का आकार_से
• रिट:=0
• नक्शे के दो किनारों और किनारों को परिभाषित करें
• जी में सभी आइटम के लिए:
  • इसे डालें[1] किनारों के अंत में[it[0]]
  लाल रंग के अंत में
  • इसे डालें[0][it[1]]
• from_cost :=inf
• एक सेट का दौरा किया और दूसरा पहुंच योग्य सेट परिभाषित करें
• एक फ़ंक्शन dfs को परिभाषित करें, यह एक संख्या लेगा i
  • अगर मैं नहीं गया और मैं पहुंच योग्य नहीं हूं, तो:
    • देखे गए में मैं सम्मिलित करें
    • किनारे में सभी j के लिए[i], करते हैं
      • dfs(j)
    • पीओ के अंत में i डालें
• फ़ंक्शन dfs2 को परिभाषित करें, यह एक नंबर लेगा मैं
• अगर मैं आ जाता हूं, तो
  • सही लौटें
• अगर मैं पहुंच योग्य हूं
  • झूठी वापसी
• मुझे विज़िट किया गया के रूप में चिह्नित करें और i को पहुंच योग्य के रूप में चिह्नित करें
• रिट:=सच
• सभी j के लिए redges[i], do
  • ret :+ ret और dfs2(j)
• रिटर्न रिटर्न
• एक कतार q परिभाषित करें
• पहुंच योग्य में 0 डालें और q में 0 डालें
• जबकि (क्यू खाली नहीं है), करें:
  • नोड:=q का पहला तत्व
  • q से तत्व हटाएं
  • किनारों में प्रत्येक i के लिए[नोड]
    • अगर मैं पहुंच योग्य नहीं हूं, तो:
      • i को रीचेबल में डालें, i को q में डालें
    • से_लागत :=न्यूनतम से_लागत और लागत_से[नोड]
• global_min :=लागत का न्यूनतम तत्व
• रिट:=रेट + से_कॉस्ट - ग्लोबल_मिन
• एक सरणी पीओ परिभाषित करें
• मैं के लिए 0 से n की सीमा में, करते हैं
  • dfs(i)
• सरणी को उल्टा करें
• पीओ में प्रत्येक के लिए, करते हैं
  • अगर मैं पहुंच योग्य हूं, तो:
    • अगले पुनरावृत्ति के लिए जाएं
  • विज़िट किए गए सरणी को साफ़ करें
  • प्रारंभिक:=dfs2(i)
  • यदि प्रारंभिक सत्य है, तो:
    • सर्वश्रेष्ठ:=जानकारी
    • विज़िट किए गए प्रत्येक j के लिए:
      • सर्वश्रेष्ठ:=न्यूनतम सर्वोत्तम और लागत_से[j]
    • ret :=ret + global_min + best
• रिटर्न रिटर्न

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

उदाहरण

#include
using namespace std;
class Solution {
   public:
   int solve(vector& costs_from, vector& costs_to, vector>& g) {
      int n = costs_from.size();
      int ret = 0;
      map> edges;
      map> redges;
      for (auto& it : g) {
         edges[it[0]].push_back(it[1]);
         redges[it[1]].push_back(it[0]);
      }
      int from_cost = INT_MAX;
      set visited;
      set reachable;
      queue 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 po;
      function dfs;
      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 dfs2;
      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 solve(vector& costs_from, vector& costs_to, vector>& edges) {
   return (new Solution())->solve(costs_from, costs_to, edges);
}
int main(){
   vector costs_from = {6, 2, 2, 12};
   vector costs_to = {2, 2, 3, 2};
   vector> edges = {{0, 3}};
   cout << solve(costs_from, costs_to, edges);
}

इनपुट

{6, 2, 2, 12}, {2, 2, 3, 2}, {{0, 3}}

आउटपुट

13