798236606 发表于 2020-2-18 16:55:40

PTA A_1076 Forwards on Weibo

本帖最后由 798236606 于 2020-2-18 16:55 编辑

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736

解：
BFS
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

const int maxn = 1010;

int n, l, k;
vector<int> adj;
int inq;

int BFS(int id)
{
    memset(inq, 0, sizeof(inq));
    queue< pair<int, int> > q;
    int num = -1;

    q.push(make_pair(id, 0));
    inq = 1;

    while (!q.empty())
    {
      id = q.front().first;
      int layer = q.front().second;

      num++;
      q.pop();

      if (layer == l) continue;

      for (int i = 0; i < adj.size(); i++)
            if (!inq] && ++inq])
                q.push(make_pair(adj, layer + 1));
    }

    return num;
}

int main(void)
{
    scanf("%d %d", &n, &l);
    for (int i = 1; i <= n; i++)
    {
      int m;

      scanf("%d", &m);
      while (m--)
      {
            int x;

            scanf("%d", &x);
            adj.push_back(i);
      }   
    }

    scanf("%d", &k);
    while (k--)
    {
      int id;

      scanf("%d", &id);
      printf("%d\n", BFS(id));
    }

    return 0;
}
页: [1]
查看完整版本: PTA A_1076 Forwards on Weibo