在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。其中近卫军团在1号隘口，天灾军团在n号隘口。某一天，天灾军团的领袖巫妖王决定派兵攻打近卫军团，天灾军团的部队如此庞大，甚至可以填江过河。但是巫妖王不想付出不必要的代价，他想知道在不修建任何通道的前提下，部队是否可以通过隘口及其相关通道到达近卫军团展开攻击；如果可以的话，最少需要经过多少通道。由于n的值比较大（n<=1000），于是巫妖王找到了擅长编程的你 =_=，请你帮他解决这个问题，否则就把你吃掉变成他的魔法。为了拯救自己，赶紧想办法吧。
输入
输入包含多组，每组格式如下。
第一行包含两个整数n,m（分别代表n个隘口，这些隘口之间有m个通道）。
下面m行每行包含两个整数a，b；表示从a出发有一条通道到达b隘口（注意：通道是单向的）。
输出
如果天灾军团可以不修建任何通道就到达1号隘口，那么输出最少经过多少通道，否则输出NO。
示例输入
2 1
1 2
2 1
2 1
示例输出
NO
1
01.#include<stdio.h>
02.#include<stdlib.h>
03.#include<
string.h>
04.
int n,m,mapp[
1010][
1010],vis[
1010];
05.
struct Node
06.{
07.
int num;
08.
int step;
09.} que[
1010*
1010],t;
10.
11.
void bfs()
12.{
13.
int r =
1,l =
0;
14. que[
0].num=
n;
15. que[
0].step=
0;
16. vis[n]=
1;
17.
while(l<
r)
18. {
19. t=que[l++
];
20.
if(t.num ==
1)
21. {
22. printf(
"%d\n",t.step);
23.
return ;
24. }
25.
for(
int i =
1; i <=
1010; i++
)
26. {
27.
if(!vis[i]&&
mapp[t.num][i])
28. {
29. que[r].num =
i;
30. que[r++].step = t.step +
1;
31. vis[i] =
1;
32. }
33. }
34. }
35. printf(
"NO\n");
36.
37.}
38.
int main ()
39.{
40.
int a,b;
41.
while(~scanf(
"%d%d",&n,&
m))
42. {
43. memset(mapp,
0,
sizeof(mapp));
44. memset(vis,
0,
sizeof(vis));
45.
for(
int i =
0; i < m; i++
)
46. {
47. scanf(
"%d %d",&a,&
b);
48. mapp[a][b] =
1;
49. }
50. bfs();
51. }
52.
return 0;
53.}
54.
55.
56.
转载于:https://www.cnblogs.com/LK1994/archive/2013/04/14/3019682.html
