目錄
- 題意
- 注意點
- 題解
題意
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;
}