PAT A1106 Lowest Price in Supply Chain
题目
找深度最小的叶子结点
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100100;
const int INF=1e12;
vector<int>Node [maxn];
double p,r,ans=INF;
int n,num=0 ;//n结点个数 m价格最低的叶子结点个数
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;
}else if(price==ans){
num++;
}
return;
}
for(int i=0; i<Node[index].size();i++){
DFS(Node[index][i], depth+1);
}
}
int main(){
int temp,k;
scanf("%d %lf %lf",&n,&p,&r);
r/=100;
for(int i=0;i<n;i++){
scanf("%d",&k);
if(k!=0){
for(int j=0;j<k;j++){
scanf("%d",&temp);
Node[i].push_back(temp);
}
}
}
DFS(0, 0);
printf("%.4f %d\n",ans,num);
return 0;
}