【PAT甲级】1106 Lowest Price in Supply Chain (25分)

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 vector<int>v[100007];
 5 int store[100007];
 6 void dfs(int x,int y){
 7     if(v[x].size()==0)
 8         store[x]=y;
 9     for(auto it:v[x]){
10         dfs(it,y+1);
11     }
12 }
13 int main(){
14     ios::sync_with_stdio(false);
15     cin.tie(NULL);
16     cout.tie(NULL);
17     int n;
18     cin>>n;
19     double p,r;
20     cin>>p>>r;
21     for(int i=0;i<n;++i){
22         int x;
23         cin>>x;
24         for(int j=1;j<=x;++j){
25             int y;
26             cin>>y;
27             v[i].push_back(y);
28         }
29     }
30     dfs(0,0);
31     int mn=1e9;
32     for(int i=0;i<n;++i)
33         if(store[i])
34             mn=min(mn,store[i]);
35     int num=0;
36     if(mn==1e9)
37         mn=0;
38     for(int i=0;i<n;++i)
39         if(store[i]==mn)
40             ++num;
41     double ans=pow(1.0+r/100,mn);
42     ans*=p;
43     printf("%.4lf %d",ans,num);
44     return 0;
45 }