PAT 1106

题目 ： Lowest Price in Supply Chain

分值 ： 25
难度 ： 简单题
思路 ： 直接根据输入建🌲,然后层序遍历数层数就可以.
坑点 ： 如果用 float去接题目中的 P和r 会有测试点过不去
       然后就是 vector<vector<int>> 先用一个 vector<int>去承接，然后再push_back()进去

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector <vector<int>> Tree ;
vector <int > v ;
int Q[100001];
int deep[100001];
int is_leave[100001];
int main() {
    int N ;
    double P , r ;
    cin >> N >> P >> r ;
    for(int i = 0 ; i< N ; i++)
    {
        int K ;
        cin >> K ;
        v.clear() ;
        for(int j = 0 ; j < K ; j++)
        {
            int temp ;
            cin >> temp ;
            v.push_back(temp) ;
        }
        Tree.push_back(v);
    }
    int count = 0  ,cur = 0 ;
    Q[count++] = 0 ;
#if 1
    while(cur <count)
    {
        int now = Q[cur];
        if(Tree[now].size() )
        {
            for(int i = 0 ; i< Tree[now].size(); i++ )
            {
                Q[count ++] = Tree[now][i] ;
                deep[ Tree[ now ][i]] = deep[now]+1 ;
            }
        }
        else
            is_leave[now] = 1 ;
        cur ++;
    }
    int min = N ,cnt = 0 ;
    for(int i = 0 ; i< N ; i++)
    {
        if(!is_leave[i]) continue;
        if(deep[i] <min)
        {
            min = deep[i] ;
            cnt =1 ;
        }
        else if(deep[i] == min)
        {
            cnt++ ;
        }
    }
    printf("%.4lf %d\n",P*pow(1+r/100.0 , min ) , cnt );
#endif
}