当前位置:   article > 正文

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

4225: 小杨做题(gesp 23年12月 2级第1题) 时间限制:1.000s 内存限制:128mb 题目描

题目描述

有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;
}

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/707105
推荐阅读
相关标签
  

闽ICP备14008679号