个人练习-PAT甲级-1106 Lowest Price in Supply Chain

本文主要是介绍个人练习-PAT甲级-1106 Lowest Price in Supply Chain，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805362341822464

题目大意：给出批发商和零售商的树状关系，每一次中转价格提高r%，求可能从零售商处获得的最低价格。

思路：就是DFS，零售商就是叶子结点。

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>using namespace std;vector<int> tree[100001];
int N, cnt = 0;
double P, r, min_price = 1e10 + 1.0;void DFS(int idx, double now_price) {if (tree[idx].size() == 0) {if (now_price < min_price) {min_price = now_price;cnt = 1;}else if (now_price == min_price)cnt++;else;}else {for (int i = 0; i < tree[idx].size(); i++)DFS(tree[idx][i], now_price * (1.0 + r/100.0));}}int main() {scanf("%d %lf %lf", &N, &P, &r);for (int i = 0; i < N; i++) {int K;scanf("%d", &K);for (int j = 0; j < K; j++) {int tmp;scanf("%d", &tmp);tree[i].push_back(tmp);}}DFS(0, P);printf("%.4f %d", min_price, cnt);return 0;
}

这篇关于个人练习-PAT甲级-1106 Lowest Price in Supply Chain的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---