C++で最初の都市から任意の都市に到達するために作成する必要のある道路の最小数を見つけるためのプログラム

同じサイズの2つのリストcosts_fromとcosts_toがあり、各インデックスiが都市を表すとします。都市iからjへの片道を作成しており、そのコストはcosts_from [i] +cost_to[j]です。また、各エッジに[x、y]が含まれているエッジのリストもあります。これは、都市xからyへの一方通行の道路がすでに存在することを示しています。都市0から任意の都市に行きたい場合は、必要な道路を建設するための最小コストを見つける必要があります。

したがって、入力がcosts_from =[6、2、2、12] cost_to =[2、2、3、2] edge =[[0、3]]のようである場合、出力は13になります。コスト9で0から2になります。その後、コスト4で2から1に進むことができます。そして、0から3に進む道がすでにあります。したがって、合計は9 + 4=13です。

これを解決するには、次の手順に従います-

• n：=costs_fromのサイズ
• ret：=0
• 2つのマップエッジと赤みを定義します
• g：
  のすべてのアイテム
  • エッジの端にit[1]を挿入します[it[0]]
  • redges [it [1]]
  の最後にit[0]を挿入します
• from_cost：=inf
• 訪問したセットと到達可能なセットを定義します
• 関数dfsを定義します。これには、数i
  が必要です。
  • 私が訪問されておらず、到達できない場合は、次のようになります。
    • 訪問先にiを挿入
    • edge [i]のすべてのjについて、
      を実行します。
      • dfs（j）
    • poの最後にiを挿入
• 関数dfs2を定義します。これには、数iが必要です
• 私が訪問された場合、
  • trueを返す
• 到達可能かどうか
  • falseを返す
• iを訪問済みとしてマークし、iを到達可能としてマークします
• ret：=true
• redges [i]のすべてのjについて、
  • ret：+ ret AND dfs2（j）
• return ret
• 1つのキューを定義するq
• 到達可能範囲に0を挿入し、qに0を挿入します
• （qは空ではありません）、次のようにします。
  • node：=qの最初の要素
  • qから要素を削除
  • エッジの各iに対して[ノード]
    • iが到達不能の場合、次のようになります。
      • iを到達可能に挿入し、iをqに挿入します
    • from_cost：=from_costとcosts_from[node]の最小値
• global_min：=costs_fromの最小要素
• ret：=ret + from_cost --global_min
• 配列poを定義する
• 0からnの範囲のiについては、
  • dfs（i）
• 配列poを逆にする
• poの各iについて、
  • 到達可能であれば、次のようになります。
    • 次の反復に進む
  • 訪問したアレイをクリアする
  • 初期：=dfs2（i）
  • イニシャルがtrueの場合、次のようになります。
    • best：=inf
    • 訪問した各jについて：
      • best：=最小のbestとcosts_to [j]
    • ret：=ret + global_min + best
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#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