Statistic?Discuss

Problem Description

?在古老的魔獸傳說中，有兩個軍團，一個叫天災，一個叫近衛。在他們所在的地域，有n個隘口，編號為1..n，某些隘口之間是有通道連接的。其中近衛軍團在1號隘口，天災軍團在n號隘口。某一天，天災軍團的領袖巫妖王決定派兵攻打近衛軍團，天災軍團的部隊如此龐大，甚至可以填江過河。但是巫妖王不想付出不必要的代價，他想知道在不修建任何通道的前提下，部隊是否可以通過隘口及其相關通道到達近衛軍團展開攻擊；如果可以的話，最少需要經過多少通道。由于n的值比較大（n<=1000），于是巫妖王找到了擅長編程的你 =_=，請你幫他解決這個問題，否則就把你吃掉變成他的魔法。為了拯救自己，趕緊想辦法吧。

?

Input

?輸入包含多組，每組格式如下。

第一行包含兩個整數n,m（分別代表n個隘口，這些隘口之間有m個通道）。

下面m行每行包含兩個整數a，b；表示從a出發有一條通道到達b隘口（注意：通道是單向的）。

?

Output

?如果天災軍團可以不修建任何通道就到達1號隘口，那么輸出最少經過多少通道，否則輸出NO。

?

Example Input

2 1 1 2 2 1 2 1

Example Output

NO 1

#include<cstdio> #include<cstring> #include<queue> using namespace std; int map[1005][1005],vis[1005]; struct node {int x,step; }temp,change; void BFS(int n) {queue <node>Q;change.x=n;change.step=0;Q.push(change);vis[n]=1;while(!Q.empty()){change=Q.front();//隊列首元素進行處理Q.pop();int i=change.x;if(i==1){printf("%d\n",change.step);return ;}for(int j=1;j<=n;j++){if(map[i][j]&&!vis[j]){vis[j]=1;temp.x=j;temp.step=change.step+1;Q.push(temp);}}}printf("NO\n"); } int main() {int n,m,x,y;while(~scanf("%d %d",&n,&m)){memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));for(int i=0;i<m;i++){scanf("%d %d",&x,&y);map[x][y]=1;}BFS(n);} }

總結

以上是生活随笔為你收集整理的sdut 2139BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。