广度优先搜索初级题目

广度优先搜索初级题目 邮递员问题 题目描述：

有一个邮递员要在n个城市之间来回送信。但有的城市之间有大路相连 而有的没有路。现在要由一个城市到另一个城市送信，中途最少要经过 多少个其它的城市呢？

输入：

第一行是n,k(1<=n<=10000, 1<=k<=20000)，接下来就是k行。

这k行每行有两个数a,b(1 <= a,b <= n)，表示城市a和b之间有大路 k行以后就是两个数p和q。 当n,k输入都为0的时候结束。

输出：

输出从城市p到城市q之间最少要经过的其它的城市的数目。 如果p和q之间不连通则输出\

样例输入1： 6 6 1 4 1 2 2 3 3 4 5 4 5 6 1 6 0 0

样例输出： 2

样例输入2： 3 1 1 2 1 3 0 0

样例输出： No solution

以下是我的代码，与大家交流分享

#include #include #include using namespace std;

intn,k;

int step[20010];

intlian[10002][10002]; int visit[20010]; intsrc,des;

int main() {

while(true) { cin>>n>>k;

if(n==0&&k==0)break; inta,b,x;

memset(lian,0,sizeof(lian)); memset(visit,0,sizeof(visit));

memset(step,10000,sizeof(step)); for(inti=0;i>a>>b; lian[a][b]=1; lian[b][a]=1; } cin>>src>>des; queue q; q.push(src); step[src]=0; visit[src]=1;

while(!q.empty()) { x=q.front(); q.pop();

for(int j=0;j<=n;j++)

{ if(lian[x][j]&&step[x]+1

} } if(!visit[des])

cout<<\else

cout<

}