心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

if(d[i,k]+d[k,j]==d[i,j])   顶点k在i到j的最短路上。

#include<stdio.h>
#define min(a,b) (a<b?a:b)
#define maxint 200000000
int main()
{
    
long g[101][101]={0},d[101][101],n,m,a,b,p,i,j,k,ans;
    scanf(
"%ld%ld",&n,&m);
    
for(i=0;i<=n;i++)
      
for(j=0;j<=n;j++)
      
{
         d[i][j]
=maxint;
         g[i][j]
=maxint;
      }

    
for(i=1;i<=m;i++)
    
{
       scanf(
"%ld%ld",&a,&b);
       g[a][b]
=1;
       g[b][a]
=1;
       d[a][b]
=1;
       d[b][a]
=1;
    }

    
for(k=1;k<=n;k++)
      
for(i=1;i<=n;i++)
        
for(j=1;j<=n;j++)
          
if(k!=&& i!=&& j!=k)
            d[i][j]
=min(d[i][j],d[i][k]+d[k][j]);
    scanf(
"%ld",&p);
    
for(i=1;i<=p;i++)
    
{
       ans
=2;
       scanf(
"%ld%ld",&a,&b);
       
for(j=1;j<=n;j++)
       
if(a!=&& d[a][j]+d[j][b]==d[a][b])
         ans
++;
       printf(
"%ld\n",ans);
    }

}

posted on 2010-01-06 19:20 lee1r 阅读(177) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:图论

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