上善若水

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  2 Posts :: 32 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

最新随笔

搜索

  •  

积分与排名

  • 积分 - 10174
  • 排名 - 1166

最新评论

阅读排行榜

评论排行榜

路径存在?

时间限制(普通/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");
    }


}
posted on 2009-11-24 11:43 上善若水 阅读(67) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理