路径存在?
时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte
总提交:295 测试通过:106
描述
对于一张有向图,判断给定的两点A,B,问是否有存在一条从A到B的路径呢?
输入
第一行为一个正整数N(1<=N<=100),表示图中的点的个数,接下来N行为该图的邻接矩阵。 第N+2行为一个整数m,表示询问的个数。 接下来m行,每行两个整数A,B(1<=A,B<=N),询问是否存在一条从A到B的路径。
输出
输出m行,按输入数据的顺序,依次回答询问。如果存在则输出yes,否则输出no
样例输入
3
1 1 0
0 1 1
0 0 1
2
1 3
3 1
样例输出
yes
no
题目来源
Narashy
分析:有向图传递闭包,多源的,所以采用Floyd-Warshall算法。但是结果不太如人意用了15ms,估计哪里出问题了,反正是ac了。
#include <stdio.h>
int main()
{
int n,i,j,k,v[101][101];
scanf("%d",&n);
for (k=0;k<n;k++)
{
for (i=0;i<n;i++)
{
scanf("%d",&v[k][i]);
}
}
for (k=0;k<n;k++)
{
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
v[i][j]=v[i][j]|v[i][k]&v[k][j];
}
}
}
scanf("%d",&n);
while (n--)
{
scanf("%d%d",&i,&j);
if (v[i-1][j-1])
{
printf("yes\n");
}
else
printf("no\n");
}
}