复习版

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#define not !
#define and &&
#define or ||

#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)

#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }

#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }

typedef long long int ll;
#define r() fast_read()

bool is_digit(const char c) {
  return c >= 48 and c <= 57;
}

ll my_pow(int base, int exponent) {
  return exponent ? my_pow(base, exponent - 1) * base : 1;
}

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not is_digit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (is_digit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

void swap(void* a, void* b, size_t size) {
  char *p = (char*) a, *q = (char*) b;
  rep(i, 0, size) *p ^= *q, *q ^= *p, *p++ ^= *q++;
}

void bubble_sort(void* base,
                 size_t num,
                 size_t size,
                 int (*compar) (const void*, const void*)) {

  rep(i, 0, num - 1) {
    bool exchange = 0;
    rep(j, 0, num - 1 - i) {
      if (compar(base + j * size, base + (j + 1) * size) > 0) {
        swap(base + j * size, base + (j + 1) * size, size);
        exchange = 1;
      }
    }
    if (not exchange) break;
  }
}


typedef int QElemType;

/* 循环队列的结构本声明  */
typedef struct {
  QElemType* base;
  size_t front, rear, capacity;
} SqQueue;

// ===================== SqQueue API =====================
bool InitQueue(SqQueue* Q, size_t capacity);

bool QueueEmpty(SqQueue* Q);

bool QueueFull(SqQueue* Q);

size_t QueueLength(SqQueue* Q);

bool EnQueue(SqQueue* Q, QElemType e);

bool DeQueue(SqQueue* Q, QElemType* e);

QElemType GetFront(SqQueue* Q);

// 第二版新增的API
QElemType GetRear(SqQueue* Q);

void CleanQueue(SqQueue* Q);

void DestroyQueue(SqQueue* Q);
// ===================== SqQueue API =====================

bool InitQueue(SqQueue* Q, size_t capacity) {
  assert(capacity > 0);

  Q->base = (QElemType*) malloc((capacity + 1) * sizeof(QElemType));
  if (!Q->base) {
    fprintf(stderr, "Failed to allocate the memory!\n");
    return false;
  }
  Q->front = Q->rear = 0;
  Q->capacity = capacity + 1;
  return true;
}

bool QueueEmpty(SqQueue* Q) {
  return Q->front == Q->rear;
}

bool QueueFull(SqQueue* Q) {
  return (Q->rear + 1) % Q->capacity == Q->front;
}

size_t QueueLength(SqQueue* Q) {
  return (Q->rear - Q->front + Q->capacity) % Q->capacity;
}

bool EnQueue(SqQueue* Q, QElemType e) {
  if (QueueFull(Q)) {
    fprintf(stderr, "The queue is full!\n");
    return false;
  }
  *(Q->base + Q->rear) = e;
  Q->rear = (Q->rear + 1) % Q->capacity;
  return true;
}

bool DeQueue(SqQueue* Q, QElemType* e) {
  if (QueueEmpty(Q)) {
    fprintf(stderr, "The queue is empty!\n");
    return false;
  }
  *e = *(Q->base + Q->front);
  Q->front = (Q->front + 1) % Q->capacity;
  return true;
}

QElemType GetFront(SqQueue* Q) {
  if (QueueEmpty(Q)) {
    fprintf(stderr, "The queue is empty!\n");
    return -0x7fffffff;
  }
  return *(Q->base + Q->front);
}

QElemType GetRear(SqQueue* Q) {
  if (QueueEmpty(Q)) {
    fprintf(stderr, "The queue is empty!\n");
    return -0x7fffffff;
  }
  return Q->base[(Q->rear - 1 + Q->capacity) % Q->capacity];
}

void CleanQueue(SqQueue* Q) {
  Q->front = Q->rear = 0;
}

void DestroyQueue(SqQueue* Q) {
  free(Q->base);
}

#define MAX_N 100010

int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
  int to, nxt;
} edges[MAX_N];

void addEdge(int u, int v) {
  edges[++edge_cnt] = (Edge) {v, head[u]};
  head[u] = edge_cnt;
}

void print_graph(const int n) {
  rep(u, 0, n) {
    printf("Vertex %d -->", u);
    for (int e = head[u]; e; e = edges[e].nxt)
      printf("[%d]\t", edges[e].to);
    putchar(10);
  }
}

int n, amounts[MAX_N];
double p, r, ans;

void DFS(int curr, int depth) {
  if (not(head[curr])) {
    ans += amounts[curr] * (p * pow((1 + r / 100), depth)); // 溢价
    return;
  }
  for (int e = head[curr]; e; e = edges[e].nxt)
    DFS(edges[e].to, depth + 1);
}

void BFS(void) {
  SqQueue Q;
  InitQueue(&Q, MAX_N);
  EnQueue(&Q, 0);

  double price = p, ans = 0.0; int curr;
  while (not QueueEmpty(&Q)) {
    size_t sz = QueueLength(&Q);
    while (sz--) {
      DeQueue(&Q, &curr);
      if (not(head[curr])) { // 零售商（即叶节点）
        ans += amounts[curr] * price;
        continue;
      }
      for (int e = head[curr]; e; e = edges[e].nxt)
        EnQueue(&Q, edges[e].to);
    }
    price *= 1 + r / 100; // 溢价
  }

  printf("%.1lf\n", ans);
  DestroyQueue(&Q);
}

signed main(int argc, char const *argv[]) {

  // freopen("test.in", "r", stdin);

  n = r();
  scanf("%lf%lf", &p, &r);
  int k;
  rep(i, 0, n) {
    k = r();
    if (not k) *(amounts + i) = r();
    else while (k--) addEdge(i, r());
  }

  // BFS();
  DFS(0, 0);
  printf("%.1lf\n", ans);

  // fclose(stdin);
  return ~~(0 ^ 0);
}

DFS + BFS Two Solutions

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;
int n, k, child;
double p, r;

unordered_map<int, int> amounts;

// depth first search
void dfs(vector<vector<int>>& g, int cur, double price, double& ans) {
  if (g[cur].empty()) { // leaf node
    ans += price * amounts[cur];
    return;
  }

  for (const auto& child : g[cur])
    // double new_price = price + price * r / 100; // 计算溢价
    dfs(g, child, price + price * r / 100, ans);
}

// breadth first search (level order)
double bfs(vector<vector<int>>& g) {

  queue<int> q{{0}};

  double ans = 0.0, price = p;
  while (not q.empty()) {
    size_t sz = q.size();
    while (sz--) {
      const int cur = q.front(); q.pop();
      if (g[cur].empty()) {
        ans += price * amounts[cur];
        continue;
      }
      for (int child : g[cur]) q.emplace(child);
    }
    price += price * r / 100; // 计算新的价格
  }

  return ans;
}

void print(vector<vector<int>>& g) {
  for (int i = 0; i < g.size(); ++i) {
    printf("%d: [", i);
    for (const auto& child : g[i]) printf("%d ", child);
    printf("]\n");
  }
}

int main(void) {
  cin >> n >> p >> r;

  vector<vector<int>> g(n); // adjacence list
  for (int i = 0; i < n; ++i) {
    scanf("%d", &k);
    if (!k) {
      int amount;
      scanf("%d", &amount);
      amounts[i] = amount;
      continue; 
    }
    while (k--) {
      scanf("%d", &child);
      g[i].emplace_back(child);
    }
  }

  // print(g);
  // double ans = 0.0;
  // dfs(g, 0, p, ans);
  // printf("%.1f", ans);

  printf("%.1f", bfs(g));
}