PAT A1106 Lowest Price in Supply Chain (25 分)

目錄

• 題意
• 注意點
• 題解

題意

PAT A1079 Total Sales of Supply Chain (25 分)

PAT A1090 Highest Price in Supply Chain (25 分)

與這兩題類似，隻不過改成了輸出最小的零售價

注意點

同上兩題

題解

解題思路：

①定義數的結點，因為不需要資料域，直接用vector數組定義

②讀入每個結點的孩子結點，建立靜态樹

③DFS函數，到最深處傳回，如果小于最小路徑則覆寫

④輸出結果

#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
const int maxn = 100010;
//定義結點
vector<int> Node[maxn];
//變量
int n;
double uniPrice, rate;
//DFS
int minPath = maxn, count = 0;
void DFS(int index, int num) {
    if (Node[index].size() == 0) {
        if (num < minPath) {
            minPath = num;
            count = 1;
        } else if (num == minPath) {
            count++;
        }
    }
    for (int i = 0; i < Node[index].size(); i++) {
        DFS(Node[index][i], num+1);
    }
}
int main() {
    scanf("%d%lf%lf", &n, &uniPrice, &rate);
    for (int i = 0; i < n; i++) {
        int childNum;
        scanf("%d", &childNum);
        for (int j = 0; j < childNum; j++) {
            int temp;
            scanf("%d", &temp);
            Node[i].push_back(temp);
        }
    }
    DFS(0, 0);
    printf("%.4f %d\n", uniPrice * pow((100+rate)*0.01, minPath), count);
    return 0;
}