当前位置: 代码迷 >> 综合 >> PAT甲级题目1106 Lowest Price in Supply Chain
  详细解决方案

PAT甲级题目1106 Lowest Price in Supply Chain

热度:52   发布时间:2024-02-01 02:39:54.0

题目大意:
供应商只有一个,经销商进货通过供应商,零售商进货通过经销商或供应商,每个商家都用0~N-1编号标出,供应商是1,现在需要求出从零售商手里买到商品最低的价格和商家数。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
const int INF = 0x3f3f3f3f;
int N;
double p, r;
vector<int> E[maxn];
int num = 0, minLevel = INF;
int vis[maxn];
void dfs(int v, int deep) 
{if (vis[v] == 1) return;vis[v] = 1;if (E[v].size() == 0){if (minLevel > deep){minLevel = deep;num = 1;}else if (deep == minLevel){num++;}}else {for (int i = 0; i < E[v].size() ; i++) {dfs(E[v][i], deep+1);}}
}
int main() 
{cin >> N >> p >> r;for (int i = 0; i < N; i++){int k;cin >> k;while (k-- ) {int d;cin >> d;E[i].push_back(d);}}num = 0;dfs(0, 0);double ans = p;for (int i = 0; i < minLevel; i++) {ans = ans*(1 + r*1.0/100.0);}printf("%.4f %d\n", ans, num);return 0;
}
  相关解决方案