LintCode 1862. 给树浇水的时间（图的遍历）

1. 题目

有一棵n个节点的树，节点编号是0至 n−1，其中 0号节点是根节点，i号节点的父亲节点是father[i] 。

现在要对树浇水，把水撒到根节点上，水会顺着每一条边流下去，从 i 号节点的父亲流到 i 号节点需要 time[i] 的时间，请问需要多久水才能流到所有节点上。

代码语言：javascript复制

样例
输入:
[-1,0,0]
[-1,3,5]
输出: 5
解释
这棵树如下所示：
   0
 3/5
1    2
从0到1需要花费3个单位时间，从0到2需要花费5个单位时间，
因此花费5个单位时间可以让水流到所有节点上。

说明
如果 father[i] = i，那么以 i 为根的子树不考虑计算。

注意事项 2≤n≤1052 leq n leq 10^52≤n≤105 0≤father[i]<n,father[0]=−10 leq father[i] < n,father[0] = -10≤father[i]<n,father[0]=−1 1≤times[i]≤1 000,time[0]=−11 leq times[i] leq 1,000, time[0] = -11≤times[i]≤1000,time[0]=−1

2. 解题

代码语言：javascript复制

class Solution {
public:
    int timeToFlowerTree(vector<int> &father, vector<int> &time) {
        int n = father.size(), id, t, maxt =0 ,i;
        vector<vector<int>> map(n);//图的邻接表
        for(i = 1; i < n;   i)
            map[father[i]].push_back(i);//from ， to
        queue<pair<int,int>> q;// id， time
        q.push({0,0});
        while(!q.empty())
        {   
            id = q.front().first;
            t = q.front().second;
            maxt = max(maxt, t);
            q.pop();
            for(i = 0; i < map[id].size();   i)
            {	//遍历邻接表
                q.push(make_pair(map[id][i], t time[map[id][i]]));
            }  
        }
        return maxt;
    }
};

1006 ms

time

0 人点赞