关系网络 时间限制：1秒 内存限制：128M_4225: 小杨做题(gesp 23年12月 2级第1题) 时间限制:1.000s 内存限制:128

题目描述

有n个人，他们的编号为1~n，其中有一些人相互认识，现在x想要认识y，可以通过他所认识的人来认识更多的人（如果a认识b，b认识c，那么a可以通过b来认识c），求出x最少需要通过多少人才能认识y

输入描述

第一行3个整数n、x、y,2<=n<=100 

接下来n行是一个nxn的邻接矩阵，a[i][j]=1表示i认识j，a[i][j]=0表示不认识。保证i=j时，a[i][j]=0,并且a[i][j]=a[j][i]

输出描述

一行一个整数，表示x认识y最少需要通过的人数。数据保证x一定能认识y

样例

输入

5 1 5
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
0 0 0 1 0

输出

2

代码：

#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int n,k,x,y,cnt=0,sum=0;
int vis[115];
int a[115][115];
int step[115];
void bfs(int x){
    q.push(x);
    vis[x]=1;
    while(q.empty()==0){
        int t=q.front();
        q.pop();
        if(t==y){
            cout<<step[y]-1;
            return ;
        }
        for(int i=1;i<=n;i++){
            if(a[t][i]==1&&vis[i]==0){
                q.push(i);
                vis[i]=1;
                step[i]=step[t]+1;
            }
        }
    }
}    
int main(){
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    bfs(x);
    return 0;
}