1079 供应链总销售额-526互联

供应链是由零售商，经销商和供应商构成的销售网络，每个人都参与将产品从供应商转移到客户的过程。

整个销售网络可以看作一个树形结构，从根部的供应商往下，每个人从上一级供应商中买入商品后，假定买入价格为 $P$ ，则会以高出买入价 $r %$ 的价格向下出售。

只有零售商（即叶节点）可以直接将产品销售给顾客。

现在，给定整个销售网络，请你计算所有零售商的总销售额。

输入格式

第一行包含三个数， $N$ 表示供应链总成员数（所有成员编号从 $0$ 到 $N - 1$ ，根部供应商编号为 $0$ ）， $P$ 表示根部供应商的每件产品的售卖价格， $r$ ，溢价百分比。

接下来 $N$ 行，每行包含一个成员的信息，格式如下：

$K_{i}$ $I D [1]$ $I D [2]$ … $I D [K_{i}]$

其中第 $i$ 行， $K_{i}$ 表示从供应商 $i$ 直接进货的成员数，接下来 $K_{i}$ 个整数是每个进货成员的编号。

如果某一行的 $K_{j}$ 为 $0$ ，则表示这是零售商，那么后面只会跟一个数字，表示卖给客户的产品总件数。

输出格式

输出总销售额，保留一位小数。

数据范围

$1 \leq N \leq 10^{5}$
$0 < P \leq 1000$ ,
$0 < r \leq 50$
每个零售商手中的产品不超过 $100$ 件。
最终答案保证不超过 $10^{10}$ 。

输入样例：

10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3

输出样例：

42.4

代码实现：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
int vis[N],c[N];
int n;
double p,r,res;
void bfs(int x){
    queue<pair<int,double> >q;
    q.push({x,p});
    while(q.size()){
        double p1=q.front().second;
        int s=q.front().first;
        q.pop();
        if(vis[s])continue;
        vis[s]=1;
        if(v[s].size()==0)res+=c[s]*p1;
        for(int i=0;i<v[s].size();i++){
            q.push({v[s][i],p1*(1+r/100)});
        }
    }
}
int main(){
    cin>>n>>p>>r;
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        if(k==0)cin>>c[i];
        else{
            while(k--){
                int x;
                cin>>x;
                v[i].push_back(x);
            }
        }
    }
    bfs(0);
    printf("%.1lf",res);
    return 0;
}