广度优先搜索练习之神奇的电梯
Time Limit: 1000MSMemory Limit: 65536KB
ProblemDescription
有一座已知层数为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。
ExampleInput
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
ExampleOutput
5
3
-1
Hint
Author
Casithy
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int tu[1010][1010];
int vist[1012];
int n,m,q;
struct node
{
int data;
int step;
}t,v;
void bfs(int x,int end)
{
queue<node>q;
t.data = x;
t.step = 0;
q.push(t);
vist[x] = 1;
while(!q.empty())
{
v = q.front();
q.pop();
if(v.data==end)
{
printf("%d\n",v.step+1);
return ;
}
for(int i=1;i<=n;i++)
{
if(!vist[i]&&tu[v.data][i])
{
t.data = i;
t.step = v.step+1;
q.push(t);
vist[i] = 1;
}
}
}
printf("-1\n");
}
//int n,m,q;
//int tu[202][202];
int main()
{
while(~scanf("%d%d%d",&n,&m,&q))
{
memset(tu,0,sizeof(tu));
for(int i=1;i<=m;i++)
{
int pos,num,k;
scanf("%d",&pos);
scanf("%d",&num);
for(int j=1;j<=num;j++)
{
scanf("%d",&k);
tu[pos][k] = 1;
}
}
for(int y=1;y<=q;y++)
{
int cc;
scanf("%d",&cc);
memset(vist,0,sizeof(vist));
bfs(1,cc);
}
}
return 0;
}
/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 164KB
Submit time: 2017-02-15 20:13:06
****************************************************/
/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 76ms
Take Memory: 2104KB
Submit time: 2017-02-16 09:03:38
****************************************************/