广度优先搜索练习之神奇的电梯

   日期:2020-10-19     浏览:100    评论:0    
核心提示:Description有一座已知层数为n的高楼,这座高楼的特殊之处在于只能靠电梯去上下楼,所以要去到某一层要非常耽误时间,然而更悲哀的是,这座高楼的电梯是限号的,小鑫最开始的时候在1层,他想去第x层,问题是他最起码要经过多少层(包含第x层)才能到达第x层。Input多组输入。第一行是三个正整数n,m,q。分别代表楼的总层数,给定的m条信息和q次查询。接下来的m行,每行的第一个整数pos代表这是第pos层的电梯,第二个数代表从这一层可以去的楼层总共有num个,之后的num个数字代表从第pos层代表可

Description
有一座已知层数为n的高楼,这座高楼的特殊之处在于只能靠电梯去上下楼,所以要去到某一层要非常耽误时间,然而更悲哀的是,这座高楼的电梯是限号的,小鑫最开始的时候在1层,他想去第x层,问题是他最起码要经过多少层(包含第x层)才能到达第x层。
Input
多组输入。
第一行是三个正整数n,m,q。分别代表楼的总层数,给定的m条信息和q次查询。
接下来的m行,每行的第一个整数pos代表这是第pos层的电梯,第二个数代表从这一层可以去的楼层总共有num个,之后的num个数字代表从第pos层代表可以去的楼层。
最后的q行,每行一个整数代表小鑫想去的楼层号码。
1<=m,pos,num<=n<=200
1<=q<=20
Output
对于每次询问输出一个整数,占一行。代表如果要去某个楼层最少要经过多少层,如果到不了的话就输出-1。
Sample
Input
10 4 3
1 2 6 7
3 4 4 6 8 10
5 2 2 3
7 3 10 5 6
4
5
9
Output
5
3
-1
这是AC代码,后面有一个wrong answer代码,求大佬指点

#include<bits/stdc++.h>
using namespace std;
int a[300][300];
int visit[300];
int dis[300];
int n,m,k;
int t;
void bfs(int x)
{ 
    visit[x]=1;
    dis[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty())
    { 
        int top=q.front();
        q.pop();
        if(top==t)
        { 
            cout<<dis[t]+1<<endl;
            return ;
        }
        for(int i=1; i<=n; i++)
        { 
            if(a[top][i]&&!visit[i])
            { 
                visit[i]=1;
                dis[i]=dis[top]+1;
                q.push(i);
                //cout<<"i="<<i<<" "<<dis[i]<<endl;
            }
        }
    }
    cout<<"-1"<<endl;
}
int main()
{ 
    while(cin>>n>>m>>k)
    { 
        memset(a,0,sizeof(a));
        for(int i=0; i<m; i++)
        { 
            int u,v;
            int kk;
            cin>>u>>kk;
            while(kk--)
            { 
                cin>>v;
                a[u][v]=1;
            }
        }
        while(k--)
        { 
            memset(visit,0,sizeof(visit));
            memset(dis,0,sizeof(dis));
            cin>>t;
            bfs(1);
        }
    }
}

求大佬指点哪里错了。。。

#include <bits/stdc++.h>

using namespace std;
vector<int>v[500];
int dis[500];
int visit[501];
int t;
void bfs(int x)
{ 
    //cout<<t<<endl;
    visit[x]=1;
    dis[x]=1;
    queue<int>q;
    q.push(x);
    while(!q.empty())
    { 
        int top=q.front();
        q.pop();
        //cout<<top<<endl;
        if(top==t)
        { 
            //cout<<endl;
            cout<<dis[t]<<endl;
            return ;
        }
        for(int i=0; i<v[top].size(); i++)
        { 
            if(!visit[v[top][i]])
            { 
                visit[v[top][i]]=1;
                dis[v[top][i]]=dis[top]+1;
                //cout<<"i="<<v[top][i]<<" "<<dis[v[top][i]]<<endl;
                q.push(v[top][i]);
            }
        }
    }
    cout<<"-1"<<endl;
}
int main()
{ 
    int n,m,q;
    while(cin>>n>>m>>q)
    { 
        for(int i=0; i<m; i++)
        { 
            int k,kk;
            cin>>k>>kk;
            while(kk--)
            { 
                int k2;
                cin>>k2;
                v[k].push_back(k2);
            }
        }
        while(q--)
        { 
            memset(visit,0,sizeof(visit));//遍历标记
            memset(dis,0,sizeof(dis));//距离记录
            cin>>t;//要到的点
            bfs(1);//从第一个点开始遍历
        }
        v[500].clear();//清空
    }
    return 0;
}

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服