C++ですべての従業員に通知するために必要な時間

会社に、従業員ごとに一意のIDを持つn人の従業員がいるとします。これらのIDの範囲は0からn-1です。会社の責任者はheadIDを持つものです。各従業員には、manager配列で指定された1人の直属の上司がいます。ここで、manager [i]はi番目の従業員の直属の上司であり、manager [headID]=-1です。また、従属関係がツリーのような構造になることが保証されています。ここで、会社の責任者は、会社のすべての従業員に緊急のニュースを通知したいと考えています。彼は直属の部下に通知することができ、すべての従業員が緊急のニュースを知るまで、部下などに通知します。 i番目の従業員は、すべての直属の部下に通知するためにinformTime [i]分が必要です（したがって、informTime [i]分後、すべての直属の部下がニュースを広め始めることができます）。緊急のニュースを全従業員に知らせるのに必要な分数を見つける必要があります。したがって、入力がn =6、headID =2、manager =[2,2、-1,2,2,2]、infromTime =[0,0,1,0,0,0]の場合、出力は1になります。

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

• ret：=0

• サイズnのグラフと呼ばれる配列を定義し、ルートを設定します：=-1

• 0からマネージャー配列のサイズまでの範囲のiの場合

  • u：=managet [i]およびv：=i

  • uが-1の場合、root：=vを設定し、次の反復に進みます

  • vをグラフに挿入[u]

• キューqを定義し、ルートをqに挿入し、サイズnのtimeという配列を定義します

• qが空になるまで

  • curr：=qのフロント要素、およびqからフロント要素を削除

  • グラフ[curr]のリストのサイズが0の場合、次の反復にスキップします

  • 0からグラフのリストのサイズまでの範囲のiの場合[curr]

    • グラフ[curr、i]をq

      に挿入します

    • time [graph [curr、i]]：=time [curr] + informTime [curr]

• 0からn– 1の範囲のiの場合：ret：=retと時間の最大値[i]

• retを返す

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
      int ret = 0;
      vector <int> graph[n];
      int root = -1;
      for(int i = 0; i < manager.size(); i++){
         int u = manager[i];
         int v = i;
         if(u == -1) {
            root = v;
            continue;
         }
         graph[u].push_back(v);
      }
      queue <int> q;
      q.push(root);
      vector <int> time(n);
      while(!q.empty()){
         int curr = q.front();
         q.pop();
         if(!graph[curr].size()) continue;
         for(int i = 0; i < graph[curr].size(); i++){
            q.push(graph[curr][i]);
            time[graph[curr][i]] = time[curr] + informTime[curr];
         }
      }
      for(int i = 0; i <n; i++)ret = max(ret, time[i]);
      return ret;
   }
};
main(){
   vector<int> v = {2,2,-1,2,2,2}, v1 = {0,0,1,0,0,0};
   Solution ob;
   cout << (ob.numOfMinutes(6, 2, v, v1));
}

入力

6
2
[2,2,-1,2,2,2]
[0,0,1,0,0,0]

出力

1