//
// Created by 高森森 on 2022/1/30.
//

#ifndef LEETCODE_SOLUTION17_H
#define LEETCODE_SOLUTION17_H
#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>

using namespace std;
class Solution17 {
public:
    vector<vector<int>>graph;
    int ans=0;
    void dfs(int pos,vector<int>&informTime,int step){
        for(int i:graph[pos]){
            dfs(i,informTime,step+informTime[pos]);
        }
        ans=max(ans,step);
    }
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        graph=vector<vector<int>>(n);
        for(int i=0;i<n;i++)
        {
            if(manager[i]!=-1)
            {
                graph[manager[i]].push_back(i);
            }
        }
        dfs(headID,informTime,0);
        return ans;
    }
    int numOfMinutes2(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        graph=vector<vector<int>>(n);
        for(int i=0;i<n;i++)
        {
            if(manager[i]!=-1)
            {
                graph[manager[i]].push_back(i);
            }
        }
        queue<vector<int>>que;
        que.push({headID,informTime[headID]});
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                auto node=que.front();
                que.pop();
                int id= node[0];
                int step=node[1];
                for(int i:graph[id]){
                    ans=max(ans,step+informTime[i]);
                    que.push({i,step+informTime[i]});
                }
            }
        }
        return ans;
    }
};


#endif //LEETCODE_SOLUTION17_H