PAT1106(BFS)

PAT 1106

思路

BFS用在tree上，这一个题里主要关注的是用vector去保存每一个节点所连接的子节点，当BFS 时，一旦发现该节点下面没有子节点，这一层一定是最短的路径，然后用当前的层数去为后面的节点做判断，如果接下来，仍然有节点没有子节点，那么用层数去验 证，如果层数一致则是，否则不是。

STL——vector

vector

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<vector>

 #include<queue>

 #define LL long long;

 using namespace std;

 const int MAXN=;

 double pi,r;

 struct node//节点

 {

     int v;//节点编号

     int cnt;//记录距离根节点的层数

 };

 vector <int> p[MAXN];//构造这棵树

 queue <node> q;

 int minct=-;

 int bfs()

 {

     int c=;

     bool flag = false;

     while(!q.empty())

     {

         node nd = q.front();

         q.pop();

         int id = nd.v;

         int ct = nd.cnt;

         //初始情况下flag记为false，也就是还未有叶子节点

         //当第一次出现有叶子节点是flag变为true

         //如果flag记为true,那么后面的节点如果还有子节点也没有必要再放进去了

         if(p[id].size()!=)

         {

             if(flag==false)

             {

                 int len = p[id].size();

                 for(int i = ;i<len;i++)

                 {

                     node tn={p[id][i],ct+};//结构体对象赋值的简化表达

                     q.push(tn);

                 }

             }

         }

         else

         {

             //如果第一次有叶子节点即（flag==false）

             //或者后面发现叶子节点层数相同（minct==ct）

             if(flag==false||minct==ct)

             {

                 flag=true;

                 minct=ct;

                 c++;

             }

         }

     }

     return c;

 }

 int main()

 {

     freopen("1106.txt","r",stdin);

     int m,k,t,s;

     cin>>m>>pi>>r;

     for(int i = ;i<m;i++)

     {

         scanf("%d",&k);

         for(int j = ;j<=k;j++)

         {

             scanf("%d",&t);

             p[i].push_back(t);

         }

     }

     node nd;

     nd.v=;

     nd.cnt=;

     q.push(nd);

     s = bfs();

     for(int i = ;i<=minct;i++)

     {

         pi=pi*(+r/100.0);

     }

     printf("%.4lf %d\n",pi,s);

     return ;

 }