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

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//key:在A1079基础上多个全局变量num记录深度最小的叶结点个数
const int maxn=100010;
const double INF=1e12; //很大的数,10^12
vector<int> Node[maxn]; //Node[i]存放i的所有孩子结点的编号
int n,num=0;  //n为结点个数，num为价格最低的叶子结点个数
double p,r,ans=INF; //ans为最低叶子结点价格
void DFS(int index,int depth){
  if(Node[index].size() == 0) { //到达叶结点
    double price=p*pow(1+r,depth);  //当前价格，每个都先算好
    if(price<ans){  //如果低于最低全局价格
      ans=price; //更新全局最低价格
      num=1;  //价格最低的叶子结点个数加1
    }else if(price == ans ){  //如果等于全局最低价格
      num++;  //价格最低的叶结点个数加1(最后要输出这类结点个数！)
    }
    return ;
  }
  for(int i=0;i<Node[index].size();i++){  
    DFS(Node[index][i], depth+1);  //递归访问子结点
  }
}
int main(){   
  int k,child;
  scanf("%d%lf%lf",&n,&p,&r); 
  r/=100;
  for(int i=0;i<n;i++){
    scanf("%d",&k);
    if(k!=0){  //叶结点标志,和1079不同，这里不用考虑k==0情况
      for(int j=0;j<k;j++){ 
        scanf("%d",&child);
        Node[i].push_back(child); //child为结点i的子结点
      }
    }
  }
  DFS(0,0); //根结点深度设为0！！
  printf("%.4f %d\n",ans,num);  //输出结果
  system("pause");
    return 0;   
}