L2-020 功夫传人

题目链接

L2-020 功夫传人

分析

BFS题，vector v[i] 存储第 $i$ 人的徒弟的编号，gl[] 存储每人的功力值，vector<pair> dy 存储得道者的编号和放大倍数，读入数据后，从祖师爷开始BFS更新每一代人的功力，最后遍历 dy 中的每一个人的功力，乘以放大倍数求和即可

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define ll long long

using namespace std;

const int MAXN = 100023;
vector<int> v[MAXN];
double gl[MAXN];
queue<int> q;
vector<pair<int, int>> dy;

int main()
{
    ll n;
    double z, r, ans = 0;
    int t, tn;
    cin >> n >> z >> r;
    r = 1 - r / 100;
    for (int i = 0; i < n; ++i)
    {
        cin >> t;
        if (t == 0)
        {
            cin >> tn;
            dy.push_back({i, tn});
            continue;
        }
        while (t--)
        {
            cin >> tn;
            v[i].push_back(tn);
        }
    }
    gl[0] = z;
    q.push(0);
    while (!q.empty())
    {
        int cn = q.front();
        q.pop();
        for (int i = 0; i < v[cn].size(); ++i)
        {
            gl[v[cn][i]] = gl[cn] * r;
            q.push(v[cn][i]);
        }
    }
    for (int i = 0; i < dy.size(); ++i)
        ans += gl[dy[i].first] * dy[i].second;
    cout << (ll)ans << endl;
}