2543: 关系网络
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:139
解决:63
题目描述
有n个人,他们的编号为1~n,其中有一些人相互认识,现在j想要认识k,可以通过他所认识的人来认识更多的人(如果a认识b、b认识c,那么a可以通过b来认识c),求出x最少需要通过多少人才能认识y。
输入
第一行三个整数n、x、y,接下来一个n×n的邻接矩阵,a[i,j]=1表示i认识j,0表示不认识。保证i=j时,a[i,j]=0,并且a[i,j]=a[j,i]。
输出
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
提示
n<=100,1<=x,y<=n,x<>y