PAT A1079 Total Sales of Supply Chain (25分)(最后一个样例超时）

本题的重点是利用层序遍历维持树每个结点的深度数据的更新，这是层序遍历的一个重要应用。
注意：计算叶子节点的次方时用#include<math.h>下的pow函数，不然最后一个样例会超时

#include<cstdio>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
const int N = 100010;
int n;
double p,r;
struct node{
    bool isretail=false;
    int amount=0;
    int deep = 0;
    vector<int> child;
}Node[N];
void updatedeep(int root){
    queue<int> Q;
    Q.push(root);
    Node[root].deep = 0;
    while(!Q.empty()){
        int front = Q.front();
        Q.pop();
        for(int i = 0;i<Node[front].child.size();i++){
            int child = Node[front].child[i];
            Node[child].deep = Node[front].deep+1;
            Q.push(child);
        }
    }
    return;
}
double price(int deep){
    double temp = p;
    double rate = 1+r/100.0;
    temp = temp*pow(rate,deep);
    return temp;
}
int main(){
    scanf("%d %lf %lf",&n,&p,&r);
    for(int i = 0;i<n;i++){
        int childnum;
        scanf("%d",&childnum);
        if(childnum==0){
            Node[i].isretail = true;
            scanf("%d",&Node[i].amount);
        }else{
            for(int j = 0;j < childnum;j++){
                int childid;
                scanf("%d",&childid);
                Node[i].child.push_back(childid);
            }
        }    
    }
    updatedeep(0);
    double total = 0;
    for(int i = 0;i<n;i++){
        if(Node[i].isretail==true){
            total += Node[i].amount*price(Node[i].deep);
        }
    }
    printf("%.1f",total);
    return 0;
}

PAT A1079 Total Sales of Supply Chain (25分)(最后一个样例超时）

原文：https://www.cnblogs.com/shuibeng/p/13633737.html